1. Sweep from left to right. If there is no 0, or no 1, or if...

 

Transcribed Image Text:

1. Sweep from left to right. If there is no 0, or no 1, or if they are out of order REJECT. 2. Move head to start. Sweep to right and search for the last 0. IF found change it to blank ELSE REJECT 3. Move head to start. Search for 0. IF found Mark it. Move right until blank. Write 2. Goto 3. 4. Search for 2. IF found Mark it. Unmark all marked 0's Shuttle between 0's and 1's. Mark one 1 for each 0 (mark 0 too). IF 0 is not found, Goto 4. IF 1 is not found, REJECT ELSE Move head to start. Search for 1. IF found REJECT. ELSE, ACCEPT. What language does the above Turing Machine recognize? 1. Sweep from left to right. If there is no 0, or no 1, or if they are out of order REJECT. 2. Move head to start. Sweep to right and search for the last 0. IF found change it to blank ELSE REJECT 3. Move head to start. Search for 0. IF found Mark it. Move right until blank. Write 2. Goto 3. 4. Search for 2. IF found Mark it. Unmark all marked 0's Shuttle between 0's and 1's. Mark one 1 for each 0 (mark 0 too). IF 0 is not found, Goto 4. IF 1 is not found, REJECT ELSE Move head to start. Search for 1. IF found REJECT. ELSE, ACCEPT. What language does the above Turing Machine recognize?