Description of the macine would be greatly appreciated Const

Description of the macine would be greatly appreciated.

Construct a Turing machine with one tape, that accepts the language {w: w contains twice as many 0s as 1s}. Assume that, at the start of the computation, the tape head is on the leftmost symbol of the input string.

Solution

A) {w : w contains twice as many 0s as 1s}

The Turing Machine(TM) should follow the steps:
1. Search from left-to-right for a 0; when one is found, write x on the cell
2. Go back to the beginning and search for a 1, if one is found, write x on the cell; if none is found,
reject.
3. Go back to the beginning and search for another 1, if one is found, write x on the cell; if none is
found, reject.
4. Go back to step 1
5. If there are only x’s then accept; otherwise, reject

By using above steps you can easily construct TM for the given language.

Description of the macine would be greatly appreciated. Construct a Turing machine with one tape, that accepts the language {w: w contains twice as many 0s as 1

Get Help Now

Submit a Take Down Notice

Tutor
Tutor: Dr Jack
Most rated tutor on our site