[Overview] [Previous] [Next]

Closure V: Right Quotient

Let L1 and L2 be languages on the same alphabet. The right quotient of L1 with L2 is
L1/L2 = {w: wx is a member of L1 and x is a member of L2}

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

Theorem. If L1 and L2 are both regular languages, then L1/L2 is a regular language.

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

For each state Qi in M(L1), determine if it should be final in M(L1/L2) as follows:

That's the basic algorithm. However, one of the steps in it is problematical: since language L2 may have an infinite number of strings, how do we determine whether some unknown string in the language is accepted by M(L1) when starting at Qi? We cannot try all the strings, because we insist on a finite algorithm.

The trick is to construct a new dfa that recognizes the intersection of two languages: (1) L2, and (2) the language that would be accepted by dfa M(L1) if Qi 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 Qi should be a final state. (Why?)

We have to go through this same process for every state Qi in M(L1), 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 L1/L2, 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