Given a Turing Machine \(M=(\{q_0, q_1, q_2, q_3\}, \{a,b\}, \{a, b, B\},…
2016
Given a Turing Machine
\(M=(\{q_0, q_1, q_2, q_3\}, \{a,b\}, \{a, b, B\}, \delta, B, \{q_3\})\)
where \(𝛿\) is a atransaction function defined as
\(𝛿(𝑞_0,𝑎)=(𝑞_1,𝑎,𝑅) \\ 𝛿(𝑞_1,𝑏)=(𝑞_2,𝑏,𝑅) \\ 𝛿(𝑞_2,𝑎)=(𝑞_2,𝑎,𝑅) \\ 𝛿(𝑞_2,𝑏)=(𝑞_3,𝑏,𝑅)\)
The language L(M) accepted by the Turing machine is given as:
- A.
\(aa^*b \) - B.
\(abab \) - C.
\(aba^*b\) - D.
\(aba^*\)
Attempted by 43 students.
Show answer & explanation
Correct answer: C
Key idea: The machine accepts exactly those strings that start with 'a', then have a 'b', then zero or more 'a's, and finally a 'b'.
From the start state q0: δ(q0,a) = (q1,a,R). So the first symbol must be 'a'; there is no transition on 'b' or blank from q0.
From q1: δ(q1,b) = (q2,b,R). So the second symbol must be 'b' to proceed; if it is 'a' there is no transition and the input is rejected.
From q2: δ(q2,a) = (q2,a,R). This allows any number of 'a's (including zero) while staying in q2.
Also from q2: δ(q2,b) = (q3,b,R). Reading a 'b' from q2 moves to the accepting state q3. Therefore a final 'b' after the a* segment is required for acceptance.
Formal description: L(M) = { a b a^n b | n ≥ 0 }.
A video solution is available for this question — log in and enroll to watch it.