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.

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.
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\}$.

Algorithm: NDFA-to-DFA Conversion
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 \ |\ \exists p \in H\left[(p,x,q) \in \Delta\right] \}$

This is actually pretty amazing: all the power of nondeterminism doesn't really buy you anything! After all,we can convert the nondeterministic machine into a deterministic machine, right? Well ... yes, but we do pay a penalty. The number of states can grow exponentially. If the NDFA has n states, there may be 2n states in the equivalent DFA!

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