Directions (Q96–100): A Turing machine for the language L = {anbmcndm | n ≥ 1, m ≥ 1} is designed. The model is M = ({q0, q1, q2, q3, q4, q5, q6, q7, qf}, {a, b, c, d}, {a, b, c, d, X1, X2, Y1, Y2, B}, δ, q0, B, {qf}), and part of δ is given in the transition table below. X1 and X2 are used to mark a's and c's, and Y1 and Y2 to mark b's and d's.
| a | b | c | d | X1 | X2 | Y1 | Y2 | B | |
|---|---|---|---|---|---|---|---|---|---|
| q0 | (q1, X1, R) | M2 | |||||||
| q1 | (q1, a, R) | (q1, b, R) | M1 | (q1, X2, R) | |||||
| q2 | (q2, a, L) | (q2, b, L) | (q2, X1, R) | (q2, X2, L) | |||||
| q3 | M3 | (q4, Y1, R) | (q6, X2, R) | ||||||
| q4 | (q4, b, R) | (q5, Y2, L) | M5 | (q4, Y2, R) | |||||
| q5 | (q5, b, L) | (q5, X2, L) | M4 | (q5, Y2, L) | |||||
| q6 | (q6, X2, R) | (q7, Y2, R) | |||||||
| q7 | (q7, Y2, R) | (qf, B, R) |
What is the move in the cell numbered M1 of the table?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. (q2, X2, L)
Explanation
q1 has run right past a's, b's and X2's to the first unmarked c. It marks it X2 and turns left in q2 to return to the a's.More Theory of Computation and Compilers questions
- What is the move in the cell numbered M2 of the table?
- What is the move in the cell numbered M3 of the table?
- What is the move in the cell numbered M4 of the table?
- What is the move in the cell numbered M5 of the table?
- The reduced grammar equivalent to the grammar whose production rules are given below is S → AB | CA B → BC | AB A → a C → aB | b
- Consider the production rules of grammar G: S → AbB A → aAb | λ B → bB | λ Which language L is generated by G?