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 M4 of the table?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. (q3, Y1, R)
Explanation
After marking a d (Y2), q5 moves left over Y2, X2 and b. On reaching the last marked b (Y1) it steps right into q3, which marks the next b or, on X2, starts the final check in q6. Without this move the b–d loop could never repeat, so it cannot be an error entry.More Theory of Computation and Compilers questions
- 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?
- Consider L = {ab, aa, baa}. Which of the following strings is NOT in L*?
- Consider the NPDA M = ({q0, q1, qf}, {a, b}, {1, z}, δ, q0, z, {qf}) with δ(q0, λ, z) = {(qf, z)} δ(q0, a, z) = {(q1, 11z)} δ(q1, a, 1) = {…