NFA to DFA conversion

 

Programs in computer know all possible transitions and states for a state machine. NFA have a transition that goes any number of states for given input and state.This is problem for a program because one transition for a given input from a given state. convert NFA to DFA eliminates this ambiguity.

NFA can have zero,one or more than one move from a given state on a given input  symbol.NFA can have NULL moves(moves without input).DFA has one and only one move from a given state on a give input symbol.

Machines used are deterministic but still for some problem NFA  is needed. Some problems need to be solve by exhaustive search(search all possible solution) and backtracking for this reason nondeterminism is used.

Example

Consider a NFA  and find equivalent DFA.

Solution

NFA  M={Q,∑,δ,,s,F) 

Here Q={s,q1,q2,qf}

    

         ∑={a,b}

        

          s is starting state.

          qf is final state.

NFA transition table is according to the state and according to the input alphabet.

• First row of  NFA  as it is in DFA transition table.

 

•  NOw two state {s} and {s,q1}. select next state is {s,q1}.  δ (s,a)={s,q1} and  δ (q1,a)=Ø  .  so δ ([s,q1],a)={s,q1}∪{Ø }={s,q1}
• δ (s,b)={s} and  δ (q1,b)=q2. so  δ ([s,q1],b)={s}∪{q2 }={s,q2}.

• Next selected state is {s,q2}
• δ (s,a)={s,q1} and  δ (q2,a)=Ø. so  δ ([s,q2],a)={s,q1}∪{Ø}={s,q1}.
• δ (s,b)={s} and  δ (q1,b)=qf. so  δ ([s,q2],b)={s}∪{qf}={s,qf}

Next selected state is {s,qf}

• δ (s,a)={s,q1} and  δ (qf,a)=Ø. so  δ ([s,qf],a)={s,q1}∪{Ø}={s,q1}.
• δ (s,b)={s} and  δ (qf,b)=Ø. so  δ ([s,q2],b)={s}∪{Ø}={s}.

DFA  after conversion NFA is