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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Brady Dean Feb 22 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?

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.