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 M3 of the table?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. (q1, X1, R)
Explanation
After returning to the last X1 and stepping right, the machine is in q3. If it reads another a, it marks it X1 and goes right in q1 to find the matching c.More Theory of Computation and Compilers questions
- 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?
- Consider L = {ab, aa, baa}. Which of the following strings is NOT in L*?