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 'M3' of the resultant Table?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. (q1,x1, R)
Explanation
The printed table is incomplete (for example, q0 has no move on b), so this cell cannot be derived cleanly from it. The official key gives (q1, X1, R).
More Theory of Computation and Compilers questions
- 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?
- Consider L = {ab, aa, baa}. Which string is NOT in L*?
- Consider the NPDA ({q0, q1, qf}, {a, b}, {1, z}, δ, q0, z, {qf}) with δ(q0, λ, z) = {(qf, z)}, δ(q0, a, z) = {(q1, 11z)}, δ(q1, a, 1) = {(q…