# Intersection of regular and not regular

$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?

• We don't know that when $L_1$ is regular and $L_2$ isn't, their intersection is always regular. Consider $L_1=\Sigma^*$. – reinierpost Dec 24 '14 at 11:17
• @reinierpost Actually, the example in the question is $L_1=\Sigma^*$ for $\Sigma=\{a\}$. – David Richerby Dec 24 '14 at 12:04
• @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. – reinierpost Dec 25 '14 at 23:01

Claim 1 if $L_1,L_2$ are regular, then $L_1 \cap L_2$ is also regular.
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)
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.