Given a Turing Machine M = ({q0 , q1 }, {0, 1}, {0, 1, B}, δ, B, {q1 }) Where…
2016
Given a Turing Machine
M = ({q0 , q1 }, {0, 1}, {0, 1, B}, δ, B, {q1 })
Where δ is a transition function defined as
δ(q0 , 0) = (q0 , 0, R)
δ(q0 , B) = (q1 , B, R) The language L(M) accepted by Turing machine is given as :
- A.
0* 1*
- B.
00*
- C.
10*
- D.
1*0*
Attempted by 43 students.
Show answer & explanation
Correct answer: B
Answer: The language is all strings consisting only of zeros (including the empty string), i.e. 0*.
Key idea: The machine scans right over zeros and accepts when it reaches the blank symbol. There is no transition for the symbol '1', so any input containing '1' is rejected.
Start state q0: on reading '0' the machine stays in q0 and moves right. So any number of consecutive zeros can be read.
On reading the blank symbol B while in q0 the machine transitions to q1 and accepts.
There is no transition for '1' in q0, so if any '1' appears in the input the machine halts without accepting (the input is rejected).
Therefore the set of accepted strings is exactly all strings of the form 0^n for n ≥ 0, i.e. 0*.
Examples: the empty string, "0", "00" are accepted; "1", "01", "10" are rejected.
A video solution is available for this question — log in and enroll to watch it.