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

**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