Past exam question: 2081 Chaitra (Regular), Q4(a)
Open in the Padhaiko appQuestion
Design a TM that recognize the . Also show how the string is accepted by your Turing machine.
Solution
Turing Machine Design Algorithm: The language has center delimiter flanked by equal numbers of 's and 's.
Operational Logic:
- In start state , if symbol is , move right into to verify that no 's remain (handles : string
c). - Mark the first as and move right into state .
- In , skip remaining 's to find center marker . Move right into .
- In , skip previously marked 's to find the first unmarked . Mark and move left into .
- In , rewind left past 's, marker , and 's until encountering . Step one cell right into and repeat.
- In , when all 's have been marked (), encountering transitions to to verify that only 's remain until blank , then halt and accept in .
Formal Specification and Automaton Block: The formal machine definition is:
| State | Read | Next State | Write | Move |
|---|---|---|---|---|
| →q0 | a | q1 | X | R |
| →q0 | c | q4 | c | R |
| q1 | a | q1 | a | R |
| q1 | c | q2 | c | R |
| q2 | Y | q2 | Y | R |
| q2 | b | q3 | Y | L |
| q3 | a | q3 | a | L |
| q3 | c | q3 | c | L |
| q3 | Y | q3 | Y | L |
| q3 | X | q0 | X | R |
| q4 | Y | q4 | Y | R |
| q4 | B | q5 | B | S |
- Machine-checked
- ✓ accepts c
- ✓ accepts acb
- ✓ accepts aacbb
- ✓ accepts aaacbbb
- ✓ accepts aaaacbbbb
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects ac
- ✓ rejects cb
- ✓ rejects aacb
- ✓ rejects acbb
- ✓ rejects cba
Execution Trace for w = aaaacbbbb: We demonstrate the acceptance of the input string ():
- Cycle 1: Replace first , cross , replace first , rewind to . Tape configuration: .
- Cycle 2: Replace second , cross , replace second , rewind to . Tape configuration: .
- Cycle 3: Replace third , cross , replace third , rewind to . Tape configuration: .
- Cycle 4: Replace fourth , cross , replace fourth , rewind to . Tape configuration: .
- Acceptance: From , reading transitions to state . The head sweeps right across all four 's: . Upon encountering the terminating blank , the transition enters accepting state and halts.
Because all 's and 's are matched and the machine terminates in accepting state , is accepted.
Answer:
The 6-state TM matches each before with a after using markers and . For (), the machine executes 4 match-and-rewind cycles, verifies all 's in state , and halts in accepting state .