Closure V: Right Quotient

Let L₁ and L₂ be languages on the same alphabet. The right quotient of L₁ with L₂ is L₁/L₂ = {w: wx

L₁ and x

L₂}

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

Theorem. If L₁ and L₂ are both regular languages, then L₁/L₂ is a regular language.

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

For each state Q_i in M(L₁), determine if it should be final in M(L₁/L₂) as follows:

Starting in state Q_i as if it were the initial state, determine if any of the strings in language L₂ are accepted by M(L₁). If there are any, then state Q_i should be marked as final in M(L₁/L₂). (Why?)

That's the basic algorithm. However, one of the steps in it is problematical: since language L₂ may have an infinite number of strings, how do we determine whether some unknown string in the language is accepted by M(L₁) when starting at Q_i? 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) L₂, and (2) the language that would be accepted by dfa M(L₁) 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₁), 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₁/L₂, this language is therefore regular, and we have shown that the regular languages are closed under right quotient.