Question

1. Give state diagrams (pictures) for Turing Machines that decide the following languages over the alphabet {0.1}: 1. {w | w contains an equal number of 0s and 1s} 2. {w | w does not contain twice as many 0s as 1s}

Answer 1

Answer:

Please kindly see explaination

Explanation:

1. Scan the tape and mark the first 1 which has not been marked. If no unmarked 1’s are

found go to stage 5. Otherwise, move the head back to the start of the tape

2. Scan the tape until an unmarked 0 is found, mark the 0, if no 0’s are found accept

3. Scan the tape once more until an unmarked zero is found, mark the 0, if no 0’s are found, accept.

4. Move the head back to the start of the tape and go to stage 1

5. Move the head back to the start of the tape. Scan the tape to see if any unmarked 0’s are

found. If none are found reject, otherwise accept.

Check attachment for the drawings.