This follows bya straightforward induction. Therefore, if δ N (p 0 , w) ∈ F, then
and if w ∈ L, then F M (w) ∈ L (H).
To complete the argument we must also show that if a string v is accepted by
H, there must be a w ∈ L, such that v = F M (w). Suppose now that instead of H
we construct another dfa H', identical to H, except that (A.5) is replaced by
δ H ’ (q ij, a ) = q kl .
The N and H' are equivalent and a string w is accepted by H' if and only if w ∈
L. Now if v ∈ L(H), then in the transition graph for H there is a path from q 00 to
a final state labeled v. But the same path in H’ is labeled w, so v = F M (w).
Therefore w ∈ L.