Proof: Let L 1 = L (M), where M = (Q,Σ, δ, q 0 , F) is a dfa. We construct another
dfa
as follows. For each q i ∈ Q, determine if there
exists a y ∈ L 2 such that
This can be done by looking at dfa's M i = (Q,Σ,δ, q i , F). The automaton M i is M
with the initial state q 0 replaced by q i . We now determine whether there exists a
y in L (M i ) that is also in L 2 . For this, we can use the construction for the
intersection of two regular languages given in Theorem 4.1, finding the
transition graph for L 2 ∩ L (M i ). If there is any path between its initial vertex and
any final vertex, then L 2 ∩ L (M i ) is not empty. In that case, add q i to .
Repeating this for every q i ∈ Q, we determine and thereby construct .
To prove that L ( ) = L 1 / L 2 , let x be any element of L 1 /L 2 . Then there must
be a y ∈ L 2 such that xy ∈ L 1 . This implies that
so that there must be some q ∈ Q such that
and
Therefore, by construction, q ∈ , and accepts x because δ* (q 0 , x) is .
Conversely, for any x accepted by , we have
But again by construction, this implies that there exists a y ∈ L 2 such that δ* (q,
y) ∈ F. Therefore, xy is in L 1 , and x is in L 1 /L 2 . We therefore conclude that