Non-deterministic Finite Automata (NDFA / NFA)

Ø The concepts of non-deterministic finite automata is exactly reverse of deterministic finite automata (DFA).

Ø The finite automata is called NFA when there exists many paths for a specific input from current state to next state.

Ø Thus it is not fixed or determined that with particular input where to go next. Hence NDFA

Ø There can be multiple final states.

Ø NFA are more flexible and easier to use than DFA.

Ø Every DFA is NFA but every NFA is not DFA.

Ø As it has finite number of states, the machine is called non-deterministic finite machine or non-deterministic finite automaton.

Ø Examples: War, weather, politics, lottery, gambling, sports etc there are various example in real life that can be related to NFA.

Graphical Representation:

Ø NFA is represented by digraphs called state diagram or transition diagram

Ø The vertices represent the states

Ø The arcs/ edges labelled with an input symbols shows the transitions

Ø Initial state is denoted by single circle and arrow pointing towards it(i.e. incoming arrow)

Ø The final state is denoted by two concentric circles

Formal definition of NFA:

Ø NFA can be represented by 5-tuple or Quintuple machine

M= (Q, ∑, δ, q₀, F), where −

· Q is a finite set of states.

· ∑ is a finite set of symbols, called the input alphabet of the automaton.

· δ is the transition function/mapping function which maps

Q x ∑ à 2^Q (Here x is cartesian Product)

Above mapping is usually represented by

1. Transition function/Mapping function

2. Transition diagram / Transition graph / Transition State diagram/ State diagram

3. Transition table/Transition state table/Mapping table

(Here power set of Q has been taken because in case of NFA ,from current state of machine, the transition can occur to any combination of Q states)

· q₀ is the initial state from where any input is processed (q₀ ∈ Q).

· F is a set of final state/states of Q (F ⊆ Q).

Ø Example : Let a NFA can be Q={A,B,C}, ∑={0,1}, q₀={A},F={C} and δ is given by the table

SOLUTION:

1)Transition function:

By using the below formula we can easily write the transition functions

δ(Present State, Input Symbol)=Next State

δ( A, 0)= {A,B} ,δ (A,1)= {B}

δ( B, 0)= {C} ,δ (B,1)= {A,C}

δ( C, 0)= {B,C} ,δ (C,1)= {C}

2)Transition diagram: