PadhaikoAll subjects

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

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Turing Machines: Representation, Moves & Computing

Question

Design a Turing machine that recognizes the language : for .

Solution

Algorithm and Marking Strategy: For language over :

Algorithm:

  1. In start state , if current symbol is blank , accept immediately ().
  2. Mark the first available with and move right in state .
  3. Skip over remaining 's and previously marked 's until finding the first . Mark with and move right in state .
  4. Skip over remaining 's and previously marked 's until finding the first . Mark with and move left in state .
  5. In state , rewind left over 's, 's, 's, and 's until encountering . Step one cell right to the next unmarked and enter .
  6. Repeat the cycle until no more 's remain.
  7. From , upon encountering , transition to to verify that all 's and 's have been fully matched (only and remain until blank ), then enter accept state .

Formal Machine Transitions and Automaton Block: The transition function is defined as:

TM for aⁿ bⁿ cⁿTM
TM for aⁿ bⁿ cⁿ Y/Y,R Z/Z,R a/a,L b/b,L Y/Y,L Z/Z,L b/b,R Z/Z,R a/a,R Y/Y,R a/X,R Y/Y,R B/B,S b/Y,R c/Z,L X/X,R B/B,S q0 q1 q2 q3 q4 q5
StateReadNext StateWriteMove
→q0aq1XR
→q0Yq4YR
→q0Bq5BS
q1aq1aR
q1Yq1YR
q1bq2YR
q2bq2bR
q2Zq2ZR
q2cq3ZL
q3aq3aL
q3bq3bL
q3Yq3YL
q3Zq3ZL
q3Xq0XR
q4Yq4YR
q4Zq4ZR
q4Bq5BS
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts abc
  • ✓ accepts aabbcc
  • ✓ accepts aaabbbccc
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects c
  • ✓ rejects ab
  • ✓ rejects bc
  • ✓ rejects aabbc
  • ✓ rejects aabcc
  • ✓ rejects ba
  • ✓ rejects acb
Answer:

The TM marks each as , finds and marks a matching as , finds and marks a matching as , and rewinds to repeat. State verifies that no unmatched symbols remain before accepting in .

All past exam questions for Theory of Computation