# If $L_1,\,L_1L_2$ are regular languages with $L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$ is $L_2$ regular?

If $$L_1,\,L_1L_2$$ are regular languages with $$L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$$ is $$L_2$$ regular?

I think I found a correct proof for this question but my professor says it cannot work. Her issue is with the right quotient step but I cannot see why it is incorrect. Can anyone shed some light on this?

$$L_1L_2 = \{ w_1w_2 : w_1 \in L_1,\, w_2 \in L_2 \} \qquad \vert w_1 \vert \ge 1,\, \vert w_2 \vert \ge1$$

$$\left( L_1L_2 \right)^R = \{ w_2^Rw_1^R : w_1 \in L_1,\, w_2 \in L_2 \}$$

$$\left( L_1L_2 \right)^R / L_1^R = \{ w_2^R : w_2 \in L_2 \} \qquad (w_1^R \in L_1^R)(\forall w_2^Rw_1^R) \implies w_2^R \in \left( L_1L_2 \right)^R / L_1^R$$

$$\left( \left( L_1L_2 \right)^R / L_1^R \right)^R = \{ w_2 : w_2 \in L_2 \} = L_2$$

$$L_2 \, \text{is regular by closure of reversal and right quotient on regular languages.}$$

How about this? $$L_1=\{a^n\mid n>0\}$$, $$L_2 = \{a^{m^2}\mid m>0\}$$. Certainly $$L_1$$ and $$L_1L_2$$ are regular, but $$L_2$$ certainly isn't.

• Took me a minute to think of how your $L_1L_2$ is regular but I see it now, nice counter example. I have a feeling my right quotient captures $L_2^R$, but also other strings. Feb 22 '20 at 0:13

Hint #1:

Try to find a counterexample.

Hint #2:

What happens in the special case where $$L_1 = \Sigma^+$$? Can you solve that special case?

Suppose $$\Sigma=\{a\}$$. Let $$L_1=\ell_{reg}=\{a^n\mid n>1\},L_2=\ell_{prime}=\{a^m\mid m\text{ is prime number}\}.$$

According to this link, $$\ell_{prime}$$ isn't regular. But $$\ell_{reg}\cdot\ell_{prime}=\ell_{reg}\cdot\{a^2,a^3,a^5,\dots\}.$$ So we can conclude that $$\ell_{reg}\cdot\ell_{prime}=a^+a^2.$$

But $$\ell_{prime}$$ isn't regular,as a result, $$L_2$$ can be non-regular.