PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q4(a)

Theory of Computation · 6 marks

Open in the Padhaiko app

Topic: Turing Machines: Representation, Moves & Computing

Question

Design a TM that recognize the language that can recognize the language : for . Check for the string for your design.

Solution

Algorithm and State Representation: The language requires matching counts of four distinct symbols across the tape.

Algorithm:

  1. In start state , if the cell is blank , accept immediately ().
  2. Replace the first unmarked with and transition to moving right.
  3. In , skip remaining 's and marked 's to find the first . Mark and enter .
  4. In , skip remaining 's and marked 's to find the first . Mark and enter .
  5. In , skip remaining 's and marked 's to find the first . Mark and enter moving left.
  6. In , rewind left past all symbols until encountering . Step one cell right to and repeat.
  7. In , when all 's have been marked as , encountering transitions to state to verify that only remain until the terminating blank , then accept in .

Formal Machine Specification: The TM is defined with tape alphabet :

TM for aⁿ bⁿ cⁿ dⁿTM
TM for aⁿ bⁿ cⁿ dⁿ X/X,R Y/Y,R Z/Z,R a/a,L b/b,L c/c,L X/X,L Y/Y,L Z/Z,L c/c,R Z/Z,R b/b,R Y/Y,R a/a,R X/X,R a/W,R X/X,R B/B,S b/X,R c/Y,R d/Z,L W/W,R B/B,S q0 q1 q2 q3 q4 q5 q6
StateReadNext StateWriteMove
→q0aq1WR
→q0Xq5XR
→q0Bq6BS
q1aq1aR
q1Xq1XR
q1bq2XR
q2bq2bR
q2Yq2YR
q2cq3YR
q3cq3cR
q3Zq3ZR
q3dq4ZL
q4aq4aL
q4bq4bL
q4cq4cL
q4Xq4XL
q4Yq4YL
q4Zq4ZL
q4Wq0WR
q5Xq5XR
q5Yq5YR
q5Zq5ZR
q5Bq6BS
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts abcd
  • ✓ accepts aabbccdd
  • ✓ accepts aaabbbcccddd
  • ✓ rejects a
  • ✓ rejects ab
  • ✓ rejects abc
  • ✓ rejects abbcd
  • ✓ rejects aabccdd
  • ✓ rejects abcdb
  • ✓ rejects dcba
  • ✓ rejects aaabbcccddd

Trace for Valid String aaabbbcccddd and Printed String aaabbcccddd: 1. For valid string ():

2. For printed string ():

Answer:

The 7-state TM marks matching 4-tuples iteratively. It accepts valid strings such as and correctly halts and rejects the printed unbalanced string due to insufficient 's.

All past exam questions for Theory of Computation