Directions (Q96–100): A Turing machine for L = {aⁿbᵐcⁿdᵐ | n ≥ 1, m ≥ 1} is designed as M = ({q0, …, q7, qf}, {a, b, c, d}, {a, b, c, d, X1, X2, Y1, Y2, B}, δ, q0, B, {qf}). X1 and X2 mark matched a's and c's; Y1 and Y2 mark matched b's and d's. Part of δ is given in the transition table (shown with each question); cells M1–M5 are to be filled.
What is the Move in the cell with number 'M1' of the resultant Table?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. (q2,X2,L)
Explanation
q1 moves right over a's, b's and marked X2's looking for the next unmarked c. On reading c it marks it X2 and turns back left (q2): (q2, X2, L).
More Theory of Computation and Compilers questions
- What is the Move in the cell with the number 'M2' of the resultant Table?
- What is the Move in the cell with number 'M3' of the resultant Table?
- What is the Move in the cell with number 'M4' of the resultant Table?
- What is the Move in the cell with number 'M5' of the resultant Table?
- The reduced grammar equivalent to S → AB | CA, B → BC | AB, A → a, C → aB | b is
- Consider the grammar G: S → AbB, A → aAb | λ, B → bB | λ. Which language does G generate?