That is, the strings in L_{1}/L_{2}
are strings from L_{1} "with their tails cut off."
If some string of L_{1} can be broken into two
parts, w and x, where x is in language L_{2},
then w is in language L_{1}/L_{2}.

**Theorem.** If L_{1} and L_{2} are both regular languages,
then L_{1}/L_{2} is a regular language.

**Proof:** Again, the proof is by construction.
We start with a dfa M(L_{1})
for L_{1}; the dfa we construct
is exactly like the dfa for L_{1}, except that
(in general) different states will be marked as final.

For each state Q_{i} in M(L_{1}),
determine if it should
be final in M(L_{1}/L_{2}) as follows:

- Starting in state Q
_{i}as if it were the initial state, determine if any of the strings in language L_{2}are accepted by M(L_{1}). If there are any, then state Q_{i}should be marked as final in M(L_{1}/L_{2}). (Why?)

The trick is to construct a new dfa that recognizes the
*intersection* of two languages: (1) L_{2},
and (2) the language that would be accepted by dfa M(L_{1})
if Q_{i} were its initial state.
We already know we can build this machine.
Now, if this machine recognizes *any string whatever*
(we can check this easily), then the two machines have a nonempty
intersection, and Q_{i} should be a final state. (Why?)

We have to go through this same process for every state Q_{i}
in M(L_{1}), so the algorithm is too lengthy to step
through by hand.
However, it is enough for our purposes that the algorithm exists.

Finally, since we can construct a dfa that recognizes
L_{1}/L_{2}, this language is therefore regular,
and we have shown that the regular languages are closed
under right quotient.

Copyright © 1996 by David Matuszek

Last modified Feb 14, 1996