Past exam question: 2082 Chaitra (Regular), Q10(b)
Open in the Padhaiko appQuestion
Design a Turing machine that recognizes the language : for .
Solution
Algorithm and Marking Strategy: For language over :
Algorithm:
- In start state , if current symbol is blank , accept immediately ().
- Mark the first available with and move right in state .
- Skip over remaining 's and previously marked 's until finding the first . Mark with and move right in state .
- Skip over remaining 's and previously marked 's until finding the first . Mark with and move left in state .
- In state , rewind left over 's, 's, 's, and 's until encountering . Step one cell right to the next unmarked and enter .
- Repeat the cycle until no more 's remain.
- 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:
- : , ,
- : , ,
- : , ,
- : , , , ,
- : , ,
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | X | R |
| →q0 | Y | q4 | Y | R |
| →q0 | B | q5 | B | S |
| q1 | a | q1 | a | R |
| q1 | Y | q1 | Y | R |
| q1 | b | q2 | Y | R |
| q2 | b | q2 | b | R |
| q2 | Z | q2 | Z | R |
| q2 | c | q3 | Z | L |
| q3 | a | q3 | a | L |
| q3 | b | q3 | b | L |
| q3 | Y | q3 | Y | L |
| q3 | Z | q3 | Z | L |
| q3 | X | q0 | X | R |
| q4 | Y | q4 | Y | R |
| q4 | Z | q4 | Z | R |
| q4 | B | q5 | B | S |
- 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 .