engineering recuitment GATE CSE 2023-24 Test Series Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Turing Machines
Consider following Turing machine M,
M = (K, Σ, Γ, δ, q0, F) where
K = {q0, q1, q2, q3}
F = {q3}
Σ = {0, 1}
Γ = {0, 1, X, Y}
δ is defined as follows:
δ(q0, 0) = (q1, X, R)
δ(q1, 0) = (q1, X, R)
δ(q1, 1) = (q2, X, R)
δ(q2, 0) = (q1, X, R)
δ(q2, 1) = (q2, X, R)
δ(q2, Y) = (q3, halt)
The Language accepted by the above Turing Machine M is:
1
{ 0n1n| n>=1 }
2
{ 0n10n | n>=1 }
3
{ 0n1n| n is a prime number }
4
{ 0(0+1)n1 | n>=0 }