CLASS 6 : NDFA / NFA Non Deterministic Finine Automata

Those finite automata which can not be determine is called NDFA.

Example:

Those finite automata which have ambiguity is called NDFA.

 Ambiguity means:  If we have multiple path for same input symbol is called ambiguity.

Here in the above figure if input is given in q1 state then it has two path q2 and q3 for selection ,so it is the case of ambiguity.

OR

We can say that if automata is in a stste {q1} and input symbol is 1 what will be the next state ? From the above figure it is clear that the next state will be the either {q2} and {q3}. Thus some machine can not determine uniquely by the input symbol, such machine are called non-deterministic automata.

Formal Definition:  A non- deterministic finite automata is a set of five tuples.

NFA = { Q , Σ , δ ,  q0 , F}

where ,
             Q    is a set of states
             Σ    is set of input symbols
             q0  is initial state
             F    is set of final state
             δ    is a transition function mapping from Q X  Σ into 2^Q which is power set of Q the set                     of all subset of Q. 
            
               δ : Q X Σ →  2^Q

Q ={q0, q1, q2, q3}      here Q = 4 states

2^{Q  = { [q0],[q1], [q2], [q3], [q0 q1], [q0 q2], [q0 q3], [q1 q0], [q1 q2], [q1 q3], [q2 q0], [q2 q1], [q2 q3], [q3 q0], [q3 q1], [q3 q2]}}