has to have certain properties. Every vertex must have exactly |Σ| outgoing
edges, each labeled with a different element of Σ. During the construction, some
of the edges may be missing, but the procedure continues until they are all there.
procedure: nfa-to-dfa
1. Create a graph G D with vertex {q 0 }. Identify this vertex as the initial vertex.
2. Repeat the following steps until no more edges are missing.
Take any vertex {q i ,q j ,…,q k } of G D that has no outgoing edge for some a ∈
Σ Compute
If
create a vertex for G D labeled {q l ,q m ,…,q n }if it does not already exist. Add
to G D an edge from {q i ,q j ,…,q k } and label it with a.
3. Every state of G D whose label contains any q f ∈ F N is identified as a final
vertex.
4. If M N accepts λ, the vertex {q 0 } in G D is also made a final vertex.
It is clear that this procedure always terminates. Each pass through the loop
in Step 2 adds an edge to G D . But G D has at most ’ 2 |Q N | |Σ| edges, so that the loop
eventually stops. To show that the construction also gives the correct answer, we
argue by induction on the length of the input string.
Assume that for every v of length less than or equal to n, the presence in G N
of a walk labeled v from q 0 to q i implies that in G D there is a walk labeled v from
{q 0 } to a state Q i = {…,q i ,…}. Consider now any w= va and look at a walk in
G N labeled w from q 0 to q 1 . There must then be a walk labeled v from q 0 to q i
and an edge (or a sequence of edges) labeled a from q i to q l . By the inductive
assumption, in G D there will be a walk labeled v from {q 0 } to Q i . But by
construction, there will be an edge from Q i to some state whose label contains q l
Thus, the inductive assumption holds for all strings of length n+ 1. As it is
obviously true for n=1, it is true for all n. The result then is that whenever
contains a final state q f , so does the label of
. To complete the
proof, we reverse the argument to show that if the label of
contains q f , so
must
edges, each labeled with a different element of Σ. During the construction, some
of the edges may be missing, but the procedure continues until they are all there.
procedure: nfa-to-dfa
1. Create a graph G D with vertex {q 0 }. Identify this vertex as the initial vertex.
2. Repeat the following steps until no more edges are missing.
Take any vertex {q i ,q j ,…,q k } of G D that has no outgoing edge for some a ∈
Σ Compute
If
create a vertex for G D labeled {q l ,q m ,…,q n }if it does not already exist. Add
to G D an edge from {q i ,q j ,…,q k } and label it with a.
3. Every state of G D whose label contains any q f ∈ F N is identified as a final
vertex.
4. If M N accepts λ, the vertex {q 0 } in G D is also made a final vertex.
It is clear that this procedure always terminates. Each pass through the loop
in Step 2 adds an edge to G D . But G D has at most ’ 2 |Q N | |Σ| edges, so that the loop
eventually stops. To show that the construction also gives the correct answer, we
argue by induction on the length of the input string.
Assume that for every v of length less than or equal to n, the presence in G N
of a walk labeled v from q 0 to q i implies that in G D there is a walk labeled v from
{q 0 } to a state Q i = {…,q i ,…}. Consider now any w= va and look at a walk in
G N labeled w from q 0 to q 1 . There must then be a walk labeled v from q 0 to q i
and an edge (or a sequence of edges) labeled a from q i to q l . By the inductive
assumption, in G D there will be a walk labeled v from {q 0 } to Q i . But by
construction, there will be an edge from Q i to some state whose label contains q l
Thus, the inductive assumption holds for all strings of length n+ 1. As it is
obviously true for n=1, it is true for all n. The result then is that whenever
contains a final state q f , so does the label of
. To complete the
proof, we reverse the argument to show that if the label of
contains q f , so
must