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 the number 'M2' of the resultant Table?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. Error entry
Explanation
q0 is entered just to the right of the last X1, so it never reads an X1. That cell is an error entry.
More Theory of Computation and Compilers questions
- 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?
- Consider L = {ab, aa, baa}. Which string is NOT in L*?