e-NFA to DFA conversion

  NFA  with NULL move that accept null input string. NFA can make a transition without reading the input string on the input tape.that transition from one state to another without any input is called null transition. NFA  with null transition is also denoted by 5-tuple M=(Q,Σ,δ,F, q0).Adding the null transition in NFA does not increase the power of  finite automata but adds some flexibility to construct NFA.

Method for constructing equivalent DFA for a given NFA  with null moves.Two operations are used for null NFA to DFA conversion.

• દ-closure()
• move()

Set of states which are reachable from state q on દ-input . That is called  દ-closure.

move(q,a) that is set of states on input a from state q.

Example:

Consider NFA with null moves find equivalent DFA.

Solution:-

In this example 

e=null input 

To convert null NFA to DFA first need to find NULL closure.

On state q0 if give input null reach on state {q0,q1,q2} that is called null closure of state q0.

Give null on state q1 does not reach on any state so mark --.

Give null on state q2 does not reach on any state so mark --.

Give null on state q4 reach on state {q4,q5,q6}.

Give null on state q5 reach on state {q5,q6}.

Give null on state q6 does not reach on any state so mark --.

Create tansition table based on Null NFA.

Conversion Null NFA to DFA

starting state is q0

null closure of q0={q0,q1,q2}

δ(q0,a)={-}

δ(q1,a)={q3}

δ(q2,a)={-}

 we get state {q3} on giving input a on state q0,q1,q2.

Again find the null closure of q3 that is {q3,q4,q5}.

δ(q0,b)={-}

δ(q1,b)={-}

δ(q2,b)={q4}

we get state {q4} on giving input b on state q0,q1,q2.

Again find the null closure of q4 that is {q4,q5,q6}.

Next state is {q3,q4,q5}

δ(q3,a)={-}

δ(q4,a)={-}

δ(q5,a)={-}

 we get state {ф} on giving input a on state {q3,q4,q5}

Again find the null closure of {ф}  that is {ф}.

δ(q3,b)={-}

δ(q4,b)={-}

δ(q5,b)={-}

we get state {ф} on giving input a on state {q3,q4,q5}.

Again find the null closure of {ф}  that is {ф}.

Nest state is {q4,q5,q6}

Next state is {q4,q5,q6}

δ(q4,a)={-}

δ(q5,a)={-}

δ(q6,a)={-}

 we get state {ф} on giving input a on state {q4,q5,q6}

Again find the null closure of {ф}  that is {ф}.

δ(q4,b)={-}

δ(q5,b)={-}

δ(q6,b)={-}

we get state {ф} on giving input a on state {q4,q5,q6}.

Again find the null closure of {ф}  that is {ф}.

No next state remain.

Transition table of DFA  After conversion.

 

DFA based on transition table

A={q0,q1,q2}

B={q3,q5,q6}

C={q4,q5,q6}