$L_1=\{a^n\mid n\ge1\}$ is regular and $L_2=\{a^{n^2}\mid n\ge1\}$ is non-regular. We know that $L_1\cap L_2$ is regular but, here $L_1\cap L_2=L_2$; and $L_2$ is not regular. How is this possible?

  • 2
    $\begingroup$ We don't know that when $L_1$ is regular and $L_2$ isn't, their intersection is always regular. Consider $L_1=\Sigma^*$. $\endgroup$ – reinierpost Dec 24 '14 at 11:17
  • $\begingroup$ @reinierpost Actually, the example in the question is $L_1=\Sigma^*$ for $\Sigma=\{a\}$. $\endgroup$ – David Richerby Dec 24 '14 at 12:04
  • $\begingroup$ @David Richerby: Yes, my remark is a clumsy way to clarify that the resulting language can always be equal to whatever you pick $L_2$ to be. $\endgroup$ – reinierpost Dec 25 '14 at 23:01

To expand a bit on David's answer, you are confusing between the next two claims.

Claim 1 if $L_1,L_2$ are regular, then $L_1 \cap L_2$ is also regular.
(proof: construct the product DFA, e.g., here)

Claim 2 if $L_1$ is regular, but $L_2$ is not, then $L_1\cap L_2$ can be either regular or not-regular.
(proof: Let $L_2$ be some non-regular language. If $L_1=\Sigma^*$ then $L_1\cap L_2=L_2$ which is non-regular by its definition. On the other hand, if $L_1=\emptyset$ then $L_1\cap L_2=L_1=\emptyset$ which is regular)

  • $\begingroup$ thanx dear for clearig my point,its cod'n is either or, but not necessary..,thnk u. $\endgroup$ – yashpal raghuwanshi Dec 26 '14 at 7:39

If $L$ and $L'$ are both regular then, yes, $L\cap L'$ is regular. But, if $L'$ is not regular, then all the bets are off, as your example shows.


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.