NFA: Nondeterministic Finite Automata Definition, Example, Application

Another type of finite automata is Non Deterministic Finite Automata (NDFAs), sometimes it is known as NFAs, does not need to obey the restrictions of finite automata as DFAs. NDFA or NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott. M.O. Robin and D. Scott also showed their equivalence to DFA.

Informally an NFA is similar to a DFA i.e, “NFAs is simple machine that used to recognize the pattern with consumes a string of input symbols or alphabet ∑. For each input symbol, it transitions to a new state until all input symbols have been consumed and machine reaches its final state”. Unlike deterministic finite automata, it is non-deterministic finite automata, which means for some state and input symbol, the next state may be nothing or one or more than one possible next states. Thus, in the formal definition of NFA, the next states in the transaction function ‘δ’ is an element of the power set of the states, which is a set of states to be considered at once. The notion of accepting an input is similar to that for the DFA. When the last input symbol from input string over alphabet ∑ is consumed, the NFA accepts if and only if there is some set of transitions that will take it to an accepting state. Equivalently, it rejects, if, no matter what transitions are applied, it would not end in an accepting state.

Also check: power of alphabet in automata

NFAs are used in the implementation of regular expressions: Thompson’s construction is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings.

Analytically a non-deterministic finite automaton is defined by five-tuples are as follows;

M = (Q, Σ, δ, q₀, F)

Where, each tuple have its specification and own definition.

1. Q: It represents the finite non-empty set states. All the finite number of states which is the part of M participates in Q.
2. Σ: It presents the non-empty finite set of the input alphabet.
3. δ : It represents the state transition function which maps Q × Σ → Q² → P(Q).
   It is usually called direct transition function. The state transition function takes the current state from Q and an input alphabet from Σ and returns the new set of output alphabets and the next state. This function mapping is usually represented by a transition table or a transition diagram.
   Here, P(Q) denotes the power set of Q. Let S = x₁x₂ … x_n be a word over the alphabet Σ. The automaton M accepts the word w if a sequence of states, r₀,r₁, …, r_n, exists in Q with the following conditions:

r₀ = q₀ (which means the machine starts in the start state q₀)
r_i+1 ∈ Δ(r_i, a_i+1), for i = 0, …, n−1 (which means given each character of string S, the machine will transition from state to state according to the transition function Δ)
r_n ∈ F (which means the machine accepts S if the last input of S causes the machine to halt in one of the accepting states).

Also check: applications and limitations of finite automata

4. q₀: It is the initial state (which may be fixed or variable depending on machine behavior). q₀ ∈ Q
5. F: It is the set of final states (F ⊆ Q). It is assumed here that there may be more than one final state.

Representation of NFAs:

A NFAs can be represented by the following ways;

1. Transaction diagram NFA or State diagram
2. Transaction table NFA
3. Language of NFA

Transaction diagram of NFA:

Transaction diagram is the graphical representation of NAFs. It is also called state diagram. To represent the behavior of a machine under NFA we are using digraph where;

• Nodes or vertices of the digraph represent the states that belong to set of states Q, and
• The connected arcs or arrow labeled with an input alphabets from ∑ that show the transition.
• The initial state is denoted by a circle with an empty single incoming arc.
• The finial state is indicated by double circles.

Transaction table of NFA:

A transaction table is a tabular representation of the behavior of transaction function δ that takes two arguments as input and returns an output state or next state. The transaction table represents all the moves of a finite semi-automata or finite state machine based on the current state and other inputs. Formally a transaction table is a 2-dimension array that consists of rows and columns where;

• The columns contain the state in which the machine will be on the input alphabet ∑ represented by that column.
• The rows corresponding to the state of the finite control unit can be in or it contains the states of the finite automata machine (current state and/or next state).
• The entry for one row corresponding to state q_i and the column corresponding to input a is the state δ(q_i, a).

Language of NFA:

The language of NFA consist a set of all strings chosen from ∑^* that all are accepted by machine M.

Example of DFA:

Represent the DFA of machine
M = ({A, B, C, D}, {a, b}, δ, A_, {B}), where δ is given as;
δ (A, a) = B,
δ (A, a) = C,
δ (A, a) = D,
δ (C, b) = A,
δ (C, b) = B,
δ (D, b) = B.

Also check: power of alphabet in automata

State transaction diagram of machine ‘M’:

State transaction table of machine ‘M’:

Language of DFA of machine ‘M’:
L_M = { a,  ab, ab*b} or
L_M = { a + ab + ab*b} or
L_M = { a + ab*b}

Application of DFA:

As we know that NFAs and DFAs are equivalent, so if a language is recognized by an NFA then it is also recognized by a DFA and vice versa. The establishment of such equivalence is important and highly applicable in various cases as follows;

• Construction of an NFA to recognize a given language is sometimes much easier than constructing a DFA for that language.
• NFAs used to reduce the complexity of the mathematical work required to establish many important properties in the theory of computation.
• NFAs is highly applicable to prove closure properties of regular languages in much easier way compare to DFAs.

Also Check: Hidden Terminal and Exposed Terminal problem and its solution