Question

Q5. [10] The left quotient of a regular language L1 with respect to L2 is defined as:
               L2/L1 = { y | x L2 , xy L1 }
Show that the family of regular languages is closed under the left quotient with a regular language.
Hint: Do NOT construct a DFA that accepts L2/L1 but use the definition of L2/L1 and the closure
properties of regular language.

Answer 1

The left quotient of a regular language L1 with respect to L2 is defined as

                  L2/L1 = {y| x ∈ L2, xy ∈ L1}

We need to show that the family of regular languages is closed under the left quotient with a regular language.

Proof:

We can take the reverse of the given language as

(L2/L1)ᴿ = {yᴿ | yᴿxᴿ ∈ L1ᴿ, xᴿ∈ L2ᴿ} = L1ᴿ / L2ᴿ -----------------(1)

But, if a language is regular then the reverse of that language is also regular (according to the closure property of regular language (Lᴿ = wᴿ : w ∈ L))

i.e., the regular languages are closed under reverse   

And , it is given that both L1 and L2 are regular so that L1ᴿ and L2ᴿ are also regular.   ------ (2)

One of the Theorem in Properties of Regular Language states that the family of regular languages is closed under right quotient with regular language.

i.e., If L1 and L2 are regular then L1/L2 is also regular   given L1/L2 = {y| xy ∈ L1, x ∈ L2}

And we have both L1ᴿ and L2ᴿ are regular. (by (2))

So according to the theorem of Regular Language

                       L1ᴿ / L2ᴿ          is also regular(right quotient) ---------------------(3)

Putting the (3) in (1) we get

(L2/L1)ᴿ is also regular ( Because, (L2/L1)ᴿ = L1ᴿ / L2ᴿ)

But, the reverse of a language is regular according to the closure property

Hence, ((L2/L1)ᴿ)ᴿ is also regular.

i.e., L2/L1 is regular.

So, the family of regular languages is closed under the left quotient.

Hence proved.