PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), 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 . 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:

  1. In start state , if symbol is , move right into to verify that no 's remain (handles : string c).
  2. Mark the first as and move right into state .
  3. In , skip remaining 's to find center marker . Move right into .
  4. In , skip previously marked 's to find the first unmarked . Mark and move left into .
  5. In , rewind left past 's, marker , and 's until encountering . Step one cell right into and repeat.
  6. 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:

TM for aⁿ c bⁿTM
TM for aⁿ c bⁿ Y/Y,R a/a,L c/c,L Y/Y,L Y/Y,R a/a,R a/X,R c/c,R c/c,R b/Y,L X/X,R B/B,S q0 q1 q2 q3 q4 q5
StateReadNext StateWriteMove
→q0aq1XR
→q0cq4cR
q1aq1aR
q1cq2cR
q2Yq2YR
q2bq3YL
q3aq3aL
q3cq3cL
q3Yq3YL
q3Xq0XR
q4Yq4YR
q4Bq5BS
  • 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 ():

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 .

All past exam questions for Theory of Computation