Non Deterministic Finite Automata

Non Deterministic Finite Automata has great importance in the theory of computation. As we learnt in the previous article, i.e., in Deterministic Finite Automata, the next input symbol is determined in the next step. But, in a Non Deterministic Finite Automata, there are several choices may exist at any point in the next state. So, every Deterministic Finite Automata is automatically a Non Deterministic Finite Automata. NFAs are used in the implementation of regular expressions.

In NFA, each state can have zero, one, two, or more transitions corresponding to a particular input symbol. It can also have an empty (ε) transition, where NFA can change state without consuming an input symbol.

Features of NFA

• NFA can perform parallel computation, multiple processes can be running concurrently.
• It can permit null or empty (ε) string transition.
• In a NFA, a state may have zero, one or many exciting arrows for each alphabet symbol. It has a choice of where to move to the next state.
• We can easily convert every NFA into an equivalent DFA.
• It is easy to understand and functionality may be easier than a DFA.

Formal definition of NFA

Non Deterministic Finite Automata also has 5 tuples.

(Q, ∑, δ, q0, F)

Q - It has a finite set of states.
∑ - Alphabet of input symbols.
δ - A transition function that takes as argument a state and a symbol and returns a state.

δ: Q × (Σ ∪ {∈}) -> p(Q)

where, P(Q) is the power set of Q.

q0 - A start state.
F - A set of final or accepting states.

A string is accepted by a NFA if δ(q0, w) contains at least one final state.

Represent NFA with Transition Table

Here is an example of an NFA using a transition table and a graph.

			0	1	ε
		q0	{q0}	{q0,q1}	∅
		q1	{q2}	{q2}	{q2}
		q2	{q3}	{q3}	∅
		q3	∅	∅	∅

NFA transition diagram of above transition table.