Intersection of regular and not regular

Question

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

• reinierpost: We don't know that when $L_1$ is regular and $L_2$ isn't, their intersection is always regular. Consider $L_1=\Sigma^*$.
• David Richerby: @reinierpost Actually, the example in the question is $L_1=\Sigma^*$ for $\Sigma=\{a\}$.
• reinierpost: @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.
• vonbrand: In your specific case, $L_1 \cap L_2 = L_2,ドル non-regular.

Answer 1

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)

• yashpal raghuwanshi: thanx dear for clearig my point,its cod'n is either or, but not necessary..,thnk u.

Answer 2

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.