Given the language A w w contains twice as many 0s and 1s

Given the language A = { w | w contains twice as many 0s and 1s}:

a. What is the implementation-level descriptions of a Turing machine that decides A?

b. What is the Turing machine, M, that decides A? (i.e., sketch it.)

Solution

Answer: Given question {w | w contains twice as many 0s as 1s}

Implementation : The Turing Machine should follow the steps:

  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. Finally, If there are only x’s then accept;

otherwise, Reject