If $L_1.L_2$ is regular, and $L_1$ is regular, then $L_2$ is regular?

298 Views Asked by At

A regular language (also called a rational language) is a formal language that can be expressed using a regular expression.

Assume that $L=L_1.L_2$ is a regular language. Also assume that $L_1$ is regular. Is it true that $L_2$ is regular too ?

Note: Please prove it using a DFA. I know how to do that with regular expressions. Thank you in advance.

1

There are 1 best solutions below

3
On BEST ANSWER

No. The empty language $\emptyset$ is regular and for every language $L$, $\emptyset L = \emptyset$ is also regular. This does not imply that $L$ is regular.

Edit. To answer your comment, here is another counterexample. Let $A$ be the alphabet. Then, for every language $L$ containing the empty word, $A^*L = A^*$. This does not imply that $L$ is regular.