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.


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.

  • $\begingroup$ Assume that $L_1$ is not empty. then what ? $\endgroup$ – Arman Malekzadeh Apr 20 '16 at 17:45
  • $\begingroup$ Also, i don't get it ... why is $\lambda.L=\lambda $?? i thought it should be equal to $L$!!! $\endgroup$ – Arman Malekzadeh Apr 20 '16 at 17:48
  • $\begingroup$ What does denote $\lambda$ for you? You seem to confuse the empty language and the language reduced to the empty word. $\endgroup$ – J.-E. Pin Apr 20 '16 at 18:43

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.