PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q12(b)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Turing Machines: Representation, Moves & Computing

Question

Design a Turing machine which reverses the given string over alphabet .

Solution

Reversal Algorithm Specification: We design a deterministic Turing Machine transducer that replaces input string on the tape with its reverse :

Algorithm:

  1. If tape is empty (), halt immediately (reverse of is ).
  2. Scan right across input to the first blank and append delimiter marker D.
  3. Sweep left to locate the rightmost unmarked symbol ( or ) of the original string. Mark it ( or ).
  4. Carry that symbol rightward past delimiter D and any previously written output symbols, appending it onto the next available blank cell.
  5. Return left past D to find the next unmarked symbol and repeat.
  6. When all symbols of the original string have been marked ( and only), move right to erase all 's, 's, and delimiter D (overwriting with blank ), leaving only the reversed string on the tape.

Formal Automaton Implementation: The formal machine specification and transitions are:

TM: String Reversal over {a, b}TM
TM: String Reversal over {a, b} X/B,R Y/B,R a/a,L b/b,L D/D,L X/X,R Y/Y,R D/D,R a/a,R b/b,R X/X,R Y/Y,R D/D,R a/a,R b/b,R X/X,L Y/Y,L a/a,R b/b,R B/B,S a/a,R b/b,R B/D,L a/X,R b/Y,R B/B,R B/a,L B/b,L X/X,L Y/Y,L D/B,R q0 q_scan q_find_right q_write_a q_write_b q_back q_clean q_done
StateReadNext StateWriteMove
→q0Bq_doneBS
→q0aq_scanaR
→q0bq_scanbR
q_scanaq_scanaR
q_scanbq_scanbR
q_scanBq_find_rightDL
q_find_rightXq_find_rightXL
q_find_rightYq_find_rightYL
q_find_rightaq_write_aXR
q_find_rightbq_write_bYR
q_find_rightBq_cleanBR
q_write_aXq_write_aXR
q_write_aYq_write_aYR
q_write_aDq_write_aDR
q_write_aaq_write_aaR
q_write_abq_write_abR
q_write_aBq_backaL
q_write_bXq_write_bXR
q_write_bYq_write_bYR
q_write_bDq_write_bDR
q_write_baq_write_baR
q_write_bbq_write_bbR
q_write_bBq_backbL
q_backaq_backaL
q_backbq_backbL
q_backDq_backDL
q_backXq_find_rightXL
q_backYq_find_rightYL
q_cleanXq_cleanBR
q_cleanYq_cleanBR
q_cleanDq_doneBR
  • Machine-checked
  • ✓ ab → ba
  • ✓ ba → ab
  • ✓ aab → baa
  • ✓ aba → aba
  • ✓ bba → abb
Answer:

The TM appends delimiter , iteratively marks the rightmost available symbol of (), copies it to the output region after , and finally erases the original marked symbols and delimiter to leave on the tape.

All past exam questions for Theory of Computation