Computation Theory 4: Equivalence of Determistic and Nondeterministic Finite Automata

Introduction:

Last module we covered what deterministic finite automata (DFA) and nondeterminitistic finite automata (NFA) are.  In this module we are going to prove that every NFA has an equivalent DFA.  This is going to be our first exposure to a formal proof that is somewhat involved.

The first question we should ask is what does it mean for two finite automata to be equivalent.  The definition of equivalence given in Spiser’s book is that finite automata are equivalent when they admit the same language.  Think about what that means for a few minutes.  Go back and review what the definition if admitting a language means if you need to.  In the mathematical sense we can rephrase the definition.

If A is the language admitted by a finite automata M then that means that A = {w | w is accepted by M}.  I may not have mentioned it previously but | means such that in set notation.  Therefore if N is an equivalent finite automata to M with language B = {v | v is accepted by N} it follows that for each v in B v is also in A.  Similarly for each w in A w is also in B.

Background Material:

The first thing we need for the proof of this is the concept of a power set.  It has been mentioned before but we are going to be more formal about it.  Given the set S = {1, 2, 3} the power set P(S) = {∅, (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3)}  which is the set of all subsets of S.

We also need to know what the union of sets is.  If we have two sets A and B then the union of A and B is A ∪ B = { x | x ∈ A or x ∈ B}.  In plain language A union B is the set of elements x such that x is an element of A or x is an element of B.

Some Things To Think About:

Think for a few minutes about the way to prove that two things are equivalent.  If I were to tell you two water buckets were equivalent how would you decide if you agreed?  It turns out that the specific property we are discussing determines how we conclude if things are equivalent.  In the case of the water buckets if we define equivalence based on shape alone then that would be very different than if we defined equivalence on capacity alone.

Lets consider how nondeterministic automata compute.  Remember that when we computed in an NFA we followed every possible path making different copies of all of the possible states at any given time.  What we want to do is capture this idea and turn it into a DFA.  But a DFA only has one possible state at a given time.  So we are going to have to combine all of the possible states of the NFA at one point in execution into one state of the DFA.

Lets Prove It:

We have nothing to prove in the case of a DFA having an equivalent NFA because a DFA is an NFA by definition.  Thus one direction of the equivalence is by definition.

The other direction of the equivalence is going to be done by construction.  We assume we have an NFA that recognizes language A and then we construct a DFA that also recognizes language A.  This is one of the proof techniques to get familiar with when dealing with math problems such as these.

Let M = {Q, ∑, δ, q0, F} be an NFA that recognizes language A.  We now need to construct each of the elements of the definition of a DFA N.  As previously stated we need to create a way to represent each step of the NFA by one state.  We are going to do this with the power set of Q.  Set QN = P(Q). Then each state of N represents a subset of the states of Q. The alphabet is the same. The transition function δN becomes a collection of transition functions as well. For each state S in QN we define the transition δN(S, a) = {q | δ(r, a) = q for some r in S}. Which means that we look at all the states of Q contained in S and take the collection of all states in Q reached by a from those states and that is the new state in QN.  Since the power set of a finite set is also finite there are still a finite number of states in N.  We leave q0 as the starting state for now. Then FN is the set of all subsets of Q that contain an accept state.

We are almost done.  We just need to deal with one last property of the NFA, the ε paths that are automatically taken.  To deal with these Sipser made a new collection for each state, E(S), which was the set of states reached by the ε automatically taken.  This set E(S) includes chains of states so any state that lies on a path of ε paths from S is included in the collection.  Thus we modify the start state as q0N =  E(q0).  We include the E(S) collection in each transition function as well.  δN(S, a) = {q | E(δ(r, a)) = q for some r in S} which could branch out to further states than the original.

That completes the construction.  N is a DFA that is defined as follows:

  • QN = P(Q)
  • ∑ = ∑
  •  δN(S, a) = {q | E(δ(r, a)) = q for some r in S}
  • q0N =  E(q0)
  • FN = {S ∈ P(Q) | there exists q ∈ F in S}

Conclusion:

The result of this theorem is that we don’t gain anything computationally with NFA’s.  Which means that any computation we can carry out on an NFA can be carried out by an equivalent DFA.  Next time we will use this property to prove that the regular operations on regular languages result in regular languages.  Which is a long way of saying that the union/concatenation/star of two regular languages is a regular language.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s