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 M2 of the table?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. Error entry
Explanation
q0 is only the start state reading the first a. It never sees X1 (later a's are handled from q3), so this cell is an error entry.More Theory of Computation and Compilers questions
- 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?
- Consider the language L = {anbm : n ≥ 4, m ≤ 3}. Which regular expression represents L?