**Reading**-
Section 2.3 of
*Theory of Computing, A Gentle Introduction* **Homework**- Printout the homework and answer the questions on that paper.

**So how do NDFAs compare to DFAs?**-
When we proposed NDFAs as a new model (since they're different
from DFAs) for a machine that computes, we gained some things
and lost some things.
- We gained flexibility in designing machines, so that it was easy to design machines for many languages that would have been difficult (impossible?) to design DFAs for.
- We gained algorithms for Kleene Star and Concatenation, which we still don't know how to do (impossible?) for DFAs.
- We lost algorithms for Intersection and Complement, which we had for DFAs.
- We lost (most importantly!) the clear connection to "real" computers. Real computers are not nondeterministic. As a consequence, we don't have the obvious translation to super-efficient programs that we get for DFAs. Moreover, it's not clear that there's any real use for NDFAs, and we don't know if they have anything to tell us about "real" computation.

Now, however, we will tie all of this together. We will show that, in one sense, DFAs and NDFAs are the same. Namely, that:

For any language $L \subseteq \Sigma^*$, there is a DFA accepting $L$ if and only if there is an NDFA accepting $L$.

This is huge and, I hope, unexpected. You would think that all the power that comes with nondeterminism would buy you something, but in terms of what languages can be accepted, it doesn't.So how will we show this remarkable fact? How else? By giving an algorithm that converts an NDFA to a DFA acccepting the same language!

**Converting NDFAs to DFAs: Part I**-
Suppose we have a nondeterministic machine
*M1*that we want to "convert" to a deterministic machine? The clever way to go about it is to keep track of all the different possible states you could be in for every new character you read.

When we start, q0 is the only possible state. When you're in q0 and you read a, you could either go to q0 or q1. When you're in q0 and you read b, you could only go to q0. When you're in q0 or q1 and you read a, you could go to either q0 or q1. When you're in q0 or q1 and you read b, you could go to either q0 or q2. When you're in q0 or q2 and you read a, you could go to either q0 or q1. When you're in q0 or q2 and you read b, you could only go to q0. Each state of this machine is labeled with all the possible states from the original nondeterministic machine that we could be in. So if we've read

*aab*, the fact that we're in state*{q0,q2}*tells us that we could be in either state q0 or q2 of the original machine, depending on which computation path we took. Now, the definition of acceptance for nondeterministic machines is that at least one of the computational paths leaves you in an accpeting state. Thus, our only accepting state would be*{q0,q2}*, since it's the only state that includes an accepting state from the original machine. So, our final machine is:

**Another Example**-
The important thing to notice in this example, is that we run
across the situation that for some strings there are no
computational paths that lead to a valid state - i.e. they all
hang somewhere. Thus, the set of states it is possible to
reach will be empty!
**An algorithm**-
Okay, lets transform this process into an algorithm! Notice
that we don't know what to do with
*λ*-transitions yet, so we'll simply define our algorithm only for machines without them:**Input:**a nondeterministic finite automaton*M = (Q,Σ,Δ,s,W)*, which has no*λ*-transitions

**Output:**a deterministic finite automaton*M'*such that*L(M') = L(M)*.*M'*is given by:

*M' = (2*, where^{Q},Σ,δ, {s}, {R ∈ 2^{Q}| R ∩ W ≠ ∅})*δ(H,x) = {q ∈Q | (p,x,q) ∈ Δ*for some*p ∈ H}**n*states, there may be*2*states in the equivalent DFA!^{n}

Christopher W Brown Last modified: Wed Sep 23 08:37:23 EDT 2009