Non-Deterministic Finite Automata (NFA)

Non-Deterministic Finite Automata (NDFA or NFA) is an automata that accepts all regular languages, whether they are finite or infinite. So, all DFA are NFA but not vice versa.

Very important In NFA is that,

•  Transition with the help of epsilon (empty string) is possible.
• There is no need to specify the transition of each input from any state.

Formal Definition of NFA

The following is the explanation of 5 tuples (Q, ∑, δ, q₀, F) of NFA where

• Q represents a finite set of all states (q_0, q_1, q_{2,   …} q_n). Where n is a finite number
• ∑ represents a finite set of symbols called the alphabet. i.e. {0, 1}.
• δ: Q x ∑ → 2^Q represents a transition function
• q₀ represents the initial state from where any input is processed (q₀ ∈ Q).
• F represents a set of final states/states where F will be a subset ( ⊆ ) of Q.

Non-Deterministic Finite Automata (NFA)  Representation

Non-Deterministic Finite Automata (NFA) examples can be represented either with epsilon or without epsilon. Let’s explain both of these 

1. Example of NFA with Epsilon

The following is an example of Non-Deterministic Finite Automata with epsilon that accepts a string 10 or epsilon.

The following is the explanation of 5 tuples of the above-given NFA

{Q {q0, q1, q2}, ∑ {0, 1}, δ, S {q0}, F {q2} }

where,

• {q0, q1, q2} are set of states
• {0, 1} are the set of input alphabets
• δ refers to the transition function
• q0 refers to the initial state
• {q2} refers to the set of final state

Transition function δ is defined as

• δ (q0, 1) = q1
• δ (q0, ∈) = q2
• δ (q1, 0) = q2

The following table shows the Transition for the above Non-Deterministic Finite Automata. 

2. Example of NFA without Epsilon

The following is an example of Non-Deterministic Finite Automata without epsilon that accepts a string 10 or 1.

The following is the explanation of 5 tuples of the above-given NFA

{ Q{ q0,q1,q2}, ∑{0,1}, δ, S{q0}, F{q2} } where 

•  {q0,q1,q2} are set of states
• {0,1} are set of input alphabets 
• δ refers to the transition function
• q0 is the initial state
• {q2} represent the final state

Transition function δ can also defined as

• δ (q0, 1) = q1
• δ (q0, 1) = q2
• δ (q1, 0) = q2 

The transition Table for the above NFA is

Equivalence of DFA and NFA

• Two finite automata accepters are considered equal in power if they both accept the same language.
• DFA and NFA both accept similar languages because DFA and NFA can be constructed for any regular language. So, both are exactly equal in power.

Important

• Every NFA is converted into its equivalent DFA.
• Every DFA is an NFA, but not every NFA is a DFA.

Let’s learn some basic examples of NFA