Question

Q6: Explain Nondeterministic Turing machines in detail. Also show how to convert non-deterministic Turing machine into deterministic Turing machine.

Answer 1

Non-Deterministic Turing Machine-:

In a Non-Deterministic Turing Machine, for every state and symbol, there are a group of actions the TM can have. So, here the transitions are not deterministic. The computation of a non-deterministic Turing Machine is a tree of configurations that can be reached from the start configuration.

An input is accepted if there is at least one node of the tree which is an accept configuration, otherwise it is not accepted. If all branches of the computational tree halt on all inputs, the non-deterministic Turing Machine is called a Decider and if for some input, all branches are rejected, the input is also rejected.

A non-deterministic Turing machine can be formally defined as a 6-tuple (Q, X, ∑, δ, q0, B, F) where −

• Q is a finite set of states

• X is the tape alphabet

• ∑ is the input alphabet

• δ is a transition function;

  δ : Q × X → P(Q × X × {Left_shift, Right_shift}).

• q0 is the initial state

• B is the blank symbol

• F is the set of final states

Conversion-:

Conversion from NDTM to DTM

In this section, we will discuss the method of converting NDTM to its equivalent DTM. In NDTM, when a specific input is given to the current state, the machine goes to multiple states. It can have zero, one or more than one move on a given input symbol. On the other hand, in DTM, when a specific input is given to the current state, the machine goes to only one state. DTM has only one move on a given input symbol.

Let, M = (Q, ∑, δ, q0, F) is an NDTM which accepts the language L(M). There should be equivalent DTM denoted by M' = (Q', ∑', q0', δ', F') such that L(M) = L(M').

Steps for converting NDTM to DTM:

Step 1: Initially Q' = ϕ

Step 2: Add q0 of NDTM to Q'. Then find the transitions from this start state.

Step 3: In Q', find the possible set of states for each input symbol. If this set of states is not in Q', then add it to Q'.

Step 4: In DTM, the final state will be all the states which contain F(final states of NDTM)

Example 1:

Convert the given NDTM to DTM.

Eg 1:- Pic 1

State	0	1
→q0	q0	q1
q1	{q1, q2}	q1
*q2	q2	{q1, q2}

Solution: For the given transition diagram we will first construct the transition table.

Now we will obtain δ' transition for state q0.

1. δ'([q0], 0) = [q0]  

2. δ'([q0], 1) = [q1]  

The δ' transition for state q1 is obtained as:

1. δ'([q1], 0) = [q1, q2]       (new state generated)  

2. δ'([q1], 1) = [q1]  

The δ' transition for state q2 is obtained as:

1. δ'([q2], 0) = [q2]  

2. δ'([q2], 1) = [q1, q2]  

Now we will obtain δ' transition on [q1, q2].

1. δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0)  

2.                       = {q1, q2} ∪ {q2}  

3.                       = [q1, q2]  

4. δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1)  

5.                       = {q1} ∪ {q1, q2}  

6.                       = {q1, q2}  

7.                       = [q1, q2]  

The state [q1, q2] is the final state as well because it contains a final state q2. The transition table for the constructed DTM will be:

State	0	1
→[q0]	[q0]	[q1]
[q1]	[q1, q2]	[q1]
*[q2]	[q2]	[q1, q2]
*[q1, q2]	[q1, q2]	[q1, q2] Date: Gg. 2. Pict3 Date Pic ; 2 G. 1 Date Pic ; 2 G. 1 (0!8

The Transition diagram will be:

Eg- 1 Pic 2-

The state q2 can be eliminated because q2 is an unreachable state.

Example 2:

Convert the given NDTM to DTM.

Eg -2 Pic -: 1

Solution: For the given transition diagram we will first construct the transition table.

State	0	1
→q0	{q0, q1}	{q1}
*q1	ϕ	{q0, q1}

Now we will obtain δ' transition for state q0.

1. δ'([q0], 0) = {q0, q1}  

2.                = [q0, q1]       (new state generated)  

3. δ'([q0], 1) = {q1} = [q1]  

The δ' transition for state q1 is obtained as:

1. δ'([q1], 0) = ϕ  

2. δ'([q1], 1) = [q0, q1]  

Now we will obtain δ' transition on [q0, q1].

1. δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0)  

2.                       = {q0, q1} ∪ ϕ  

3.                       = {q0, q1}  

4.                       = [q0, q1]  

Similarly,

1. δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1)  

2.                       = {q1} ∪ {q0, q1}  

3.                       = {q0, q1}  

4.                       = [q0, q1]  

As in the given NDTM, q1 is a final state, then in DTM wherever, q1 exists that state becomes a final state. Hence in the DTM, final states are [q1] and [q0, q1]. Therefore set of final states F = {[q1], [q0, q1]}.

The transition table for the constructed DTM will be:

State	0	1
→[q0]	[q0, q1]	[q1]
*[q1]	ϕ	[q0, q1]
*[q0, q1]	[q0, q1]	[q0, q1]

The Transition diagram will be:

Eg 2-: Pic 2

Even we can change the name of the states of DTM.

Suppose

1. A = [q0]  

2. B = [q1]  

3. C = [q0, q1]  

With these new names the DTM will be as follows:

Eq-: 2 Pic-3

Please write back for any inconvenience