Question

1. Give state diagrams (pictures) for Turing Machines that decide the following languages over the alphabet {0.1}: 1. w 2. w

Answer 1

Please kindly see explaination

Step-by-step 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.