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 'M4' of the resultant Table?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. (q3, Y1, R)
Explanation
q5 walks left over Y2's, X2's and b's after marking a d. When it reaches the last Y1 it must step right into q3 to mark the next b: (q3, Y1, R).
Note on the official key: the official key says option D. Official/PW key is D (error entry). Without a move on Y1, q5 could never return to q3 and the machine could not handle more than one b.
More Theory of Computation and Compilers questions
- 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…
- Consider two PCP instances over {0, 1}, each with lists A and B of three strings. X: A = (1, 10111, 10), B = (111, 10, 0). Y: A = (10, 011,…