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.
