Past exam question: 2082 Kartik (Back), Q4(a)
Open in the Padhaiko appQuestion
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:
- In start state , if the cell is blank , accept immediately ().
- Replace the first unmarked with and transition to moving right.
- In , skip remaining 's and marked 's to find the first . Mark and enter .
- In , skip remaining 's and marked 's to find the first . Mark and enter .
- In , skip remaining 's and marked 's to find the first . Mark and enter moving left.
- In , rewind left past all symbols until encountering . Step one cell right to and repeat.
- 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 :
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | W | R |
| →q0 | X | q5 | X | R |
| →q0 | B | q6 | B | S |
| q1 | a | q1 | a | R |
| q1 | X | q1 | X | R |
| q1 | b | q2 | X | R |
| q2 | b | q2 | b | R |
| q2 | Y | q2 | Y | R |
| q2 | c | q3 | Y | R |
| q3 | c | q3 | c | R |
| q3 | Z | q3 | Z | R |
| q3 | d | q4 | Z | L |
| q4 | a | q4 | a | L |
| q4 | b | q4 | b | L |
| q4 | c | q4 | c | L |
| q4 | X | q4 | X | L |
| q4 | Y | q4 | Y | L |
| q4 | Z | q4 | Z | L |
| q4 | W | q0 | W | R |
| q5 | X | q5 | X | R |
| q5 | Y | q5 | Y | R |
| q5 | Z | q5 | Z | R |
| q5 | B | q6 | B | S |
- 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 ():
- Cycle 1: Mark first . Tape: .
- Cycle 2: Mark second . Tape: .
- Cycle 3: Mark third . Tape: .
- Rewind to , step right into reading . Transition to sweeps right over and reaches , entering accepting state . Accepted!
2. For printed string ():
- Cycle 1: Marks first . Tape: .
- Cycle 2: Marks second . Tape: .
- Cycle 3: In , head marks third and enters . State scans right over looking for , but encounters (no left to match!).
- Since no transition exists, the machine halts in non-accepting state and rejects.
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.