Q12: Non-deterministic Turing Machine

Question #12: Following is a transition table of non-deterministic TM:

Which all of the ID’s can be reached after third transitions, when the initial ID is q₀011?

 

Options:

1. 100q₁ , 1q₀01
2. 11q₀1
3. 101q₁ , 1q₀01
4. 111q₁

 

Solution:

Transitions will be:

q₀011   |-   1q₀11

1q₀11   |- 10q₁1

10q₁1 |- 101q₁ , 1q₀01

Hence, the correct answer is option 3.