- 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!
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:
Note: "$2^{Q}$" denotes the set of all subsets of $Q$. So, for example, if $Q = \{q_0,q_1\}$, $2^Q = \left\{ \{\}, \{q_0\},\{q_1\},\{q_0,q_1\}\right\}$.
Input: a nondeterministic finite automaton $M = \left(Q,\Sigma,\Delta,s,W\right)$, which has no $\lambda$-transitions
Output: a deterministic finite automaton $M'$ such that $L(M') = L(M)$.
$ M' = \left( 2^{Q}, \Sigma, \delta, \{s\}, \{ R \in 2^{Q}\ |\ R \cap Q \neq \emptyset \} \right) $, where $\delta(H,x) = \{ q \in Q \ |\ (p,x,q) \in \Delta \text{ for some } p \in H \}$