NFA and DFA Equivalence Theorem Proof and Example

Finite state automata (FSA), also known as finite state machines (FSM), are usually classified as being deterministic (DFA) or non-deterministic (NFA). A deterministic finite state automaton has exactly one transition from every state for each possible input. In other words, whatever state the FSA is in, if it encounters a symbol for which a transition exists, there will be just one transition and obviously as a result, one follow up state. For a given string, the path through a DFA is deterministic since there is no place along the way where the machine would have to choose between more than one transition.  Given this definition it isn’t too hard to figure out what an NFA is. Unlike in DFA, it is possible for states in an NFA to have more than one transition per input symbol. Additionally, states in an NFA may have states that don’t require an input symbol at all, transitioning on the empty string ε.

Superficially it would appear that deterministic and non-deterministic finite state automata are entirely separate beasts. It turns out, however, that they are equivalent. For any language recognized by an NFA, there exists a DFA that recognizes that language and vice versa. The algorithm to make the conversion from NFA to DFA is relatively simple, even if the resulting DFA is considerably more complex than the original NFA.  After the jump I will prove this equivalence and also step through a short example of converting an NFA to an equivalent DFA.

NFA and DFA Equivalence Theorem Proof

Before continuing, let’s formally state the theorem we are proving:

Theorem

Let language L ⊆ Σ*, and suppose L is accepted by NFA N = (Σ, Q, q₀, F, δ). There exists a DFA D= (Σ, Q’, q’₀, F’, δ’) that also accepts L. (L(N) = L(D)).

By allowing each state in the DFA D to represent a set of states in the NFA N, we are able to prove through induction that D is equivalent to N. Before we begin the proof, let’s define the parameters of D:

• Q’ is equal to the powerset of Q, Q’ = 2^Q
• q’₀ = {q₀}
• F’ is the set of states in Q’ that contain any element of F, F’ = {q ∈ Q’|q ∩ F ≠ Ø}
• δ’ is the transition function for D.  for q ∈ Q’ and a ∈ Σ.

I think it’s worth further explaining δ’. Remember that each state in the set of states Q’ in D is a set of states itself from Q in N. For each state p in state q in Q’ of D (p is a single state from Q), determine the transition δ(p,a).  δ(q,a) is the union of all δ(p,a).

Now we will prove that for every x. ie, L(D) = L(N)

Basis Step

Let x be the empty string ε.

Inductive Step

Assume that for any y with |y| ≥ 0, .

If we let n = |y|, then we need to prove that for a string z with |z| = n + 1, . We can represent the string z as a concatenation of string y (|y| = n) and symbol a from the alphabet Σ (a ∈ Σ). So, z = ya.

DFA D accepts a string x iff . From the above it follows that D accepts x iff  .

So a string is accepted by DFA D if, and only if, it is accepted by NFA N.

NFA to DFA Conversion Example

From the proof, we can tease out an algorithm that will allow us to convert any non-deterministic finite state automaton (NFA) to an equivalent deterministic finite state automaton (DFA). That is, the language accepted by the DFA is identical that accepted by the NFA.

Algorithm

Given NFA N = (Σ, Q, q₀, F, δ) we want to build DFA D= (Σ, Q’, q’₀, F’, δ’). Here’s how:

1. Initially Q’ = ∅.
2. Add q₀ to Q’.
3. For each state in Q find the set of possible states for each input symbol using N’s transition table, δ. Add this set of states to Q’, if it is not already there.
4. The set of final states of D, F’, will be all of the the states in Q’ that contain in them a state that is in F.

Working through an example may aid in understanding these steps.

Consider the following NFA N = (Σ, Q, q₀, F, δ)

Σ = {a, b, c}
Q = {q₀, q₁, q₂}
F = {q₂}

We wish to construct DFA D= (Σ, Q’, q’₀, F’, δ’). Following the steps in the conversion algorithm:

1. Q’ = ∅
2. Q’ = {q₀}
3. For every state in Q, find the set of states for each input symbol using using N’s transition table, δ. If the set is not Q, add it to Q’.We can start building the transition table δ’ for D by first examining q₀.
   

   state	a	b	c
   q0	{q0, q1}	q0	q2

   q₀ is already in Q’ so we don’t add it.  {q₀, q₁} is  considered a single state, so we add it and q₂ to Q’.

   Q’ = {q₀, {q₀, q₁}, q₂}

   δ’ now looks like:

   state	a	b	c
   q0	{q0, q1}	q0	q2
   {q0, q1}	?	?	?
   q2	?	?	?

    

   To fill in the transitions for {q₀, q₁}, you need to determine per symbol how each individual state in the set transitions and take the union of these states.

   δ'({q₀, q₁}, a) = δ(q₀,a) ∪  δ(q₁,a) =  {q₀, q₁} ∪ ∅ = {q₀, q₁}
   δ'({q₀, q₁}, b) = δ(q₀,b) ∪  δ(q₁,b) = c ∪ {q₂} = {q₀, q₂}
   δ'({q₀, q₁}, c) = δ(q₀,c) ∪  δ(q₁,c) ={q₂} ∪ ∅ = {q₂}

   The only new state here is {q₀, q₂}. We add it to Q’:

   Q’ = {q₀, {q₀, q₁}, q₂, {q₀, q₂}}

   And update the transition table δ’:

   state	a	b	c
   q0	{q0, q1}	q0	q2
   {q0, q1}	{q0, q1}	{q0, q2}	q2
   q2	?	?	?
   {q0, q2}	?	?	?

    

   q₂ has no outgoing transitions so the transition table is simple to update.

   state	a	b	c
   q0	{q0, q1}	q0	q2
   {q0, q1}	{q0, q1}	{q0, q2}	q2
   q2	–	–	–
   {q0, q2}	?	?	?

    

   Now calculate the transitions for {q₀, q₂}:

   δ'({q₀, q₂}, a) = δ(q₀,a) ∪  δ(q₂,a) =  {q₀, q₁} ∪ ∅ = {q₀, q₁}
   δ'({q₀, q₂}, b) = δ(q₀,b) ∪  δ(q₂,b) ={q₀} ∪ ∅ ={q₀}
   δ'({q₀, q₂}, c) = δ(q₀,c) ∪  δ(q₂,c) = {q₂} ∪ ∅ = {q₂}

   There are no new states to add to Q’. The updated transition table looks like:

   state	a	b	c
   q0	{q0, q1}	q0	q2
   {q0, q1}	{q0, q1}	{q0, q2}	q2
   q2	–	–	–
   {q0, q2}	{q0, q1}	q0	q2

    

   Since we’ve inspected all of the states in Q and no longer have any states to add to Q’, we are finished. D’s set of final states F’ are those states that include states in F. So, F’ = {q₂, {q₀, q₂}}.

   For our completed DFA D= (Σ, Q’, q’₀, F’, δ’):

   • Σ = {a, b}
   • Q’ = {q₀, {q₀, q₁}, q₂, {q₀, q₂}}
   • q’₀=q₀
   • F’ = {q₂, {q₀, q₂}}
   • δ’ is:
     

     state	a	b	c
     q0	{q0, q1}	q0	q2
     {q0, q1}	{q0, q1}	{q0, q2}	q2
     q2	–	–	–
     {q0, q2}	{q0, q1}	q0	q2

The transition graph for this DFA looks like:

Again for reference, the original NFA was: