8.1 RELATIONSHIP BETWEEN NFA AND DFA
Now we will discuss the relationship between finite automatons DFA & NFA and simultane-
ously study how one form of finite automata is converted into another form of finite automata.
We know that the nondeterministic finite state automaton (NFA) provides flexibility in transi-
tions of state/s over the input symbol. But, a deterministic finite state automaton (DFA) pro-
vides the fixed or static view of transitions of states over input symbol. Hence, for the same
language it is comparatively easy to construct a NFA rather than a DFA, because DFA is the
limiting case of NFA, and each DFA must be the consisting part of a NFA.
In this section we will present the quantitative view of the relationship between a NFA
and a DFA by proving the following theorem.
Theorem 8.1. If there is an NFA accepting the language L then, there exist a DFA for the same
language L.
Proof. Let N be a NFA which is defined over following tuples: QN, Σ, δN, q0N, FN (where the
subscriptN stands for automaton NFA), i.e.,
N = (QN, Σ, ΣN, q0N, FN)
Since L is the language of a NFA N where L is given as,
LN = {x/x ∈ Σ* and δ^(q 0 , x) ∩ F ≠ Φ}
Now define a DFA M on following set of tuples, QD, δD, q0D, FD and same set of input
alphabet Σ, so
M = (QD , Σ, δD, q0D , FD); [where subscript D stands for automaton DFA]
Now, establish the correspondence between the tuples of both automatons, i.e.,
· QD with QN: The set QD contains the states that are in power set of QN. Thus, QD ⊆
P(QN). Alternatively, states of the DFA have been selected from the set of possible
states that contains a total number of states 2 QN.
· q0N with q0D: Assume both machine accelerate from same starting state hence,
{q0D} = {q0N}, Let it be {q 0 }
· Suppose x is the input string so compare the moves δ$D(q 0 , x) with $δN(q 0 ,x):
- If string x is a null string (∈) then,
δ$
N(q 0 , ∈) = q 0 ; and
δ$
D(q 0 , ∈) = q 0 ; [using Ist property of δ-head]
Hence, both automatons return to same state. - For rest of the cases of x we shall prove by using method of induction. Suppose,
string x = a 1 .a 2 .a 3 ...........an. a [∴ | x | = (n + 1) ]
8
Equivalence of NFA
and DFA
192