# Is intersection of regular language and context free language is "always" context free language

I have read that intersection of regular language and context-free language is always context-free. Most of the places an standard example has been used to prove this, e.g., \begin{align*} L_1 &= L(a^*b^*)\\ L_2 &= \{a^nb^n\mid n\geq 0\} \quad\text{(which is context free)}\\ L_1\cap L_2 &= \{a^nb^n\mid n\geq 0\}\,. \end{align*} But my question is what if the regular language is finite, such as \begin{align*} L_1 &= \{ab\}\\ L_2 &= \{a^nb^n\mid n\geq 0\}\\ L_1\cap L_2 = \{ab\}\,. \end{align*} Here intersection comes out to be finite and the language generated by intersection of both language is also finite which is regular (I know it's also context-free but regular is a stronger answer here).

What mistake am I making in understanding the concept?

• cs.stackexchange.com/questions/18642/…
– D.W.
Jun 22, 2016 at 7:04
• "Most of the places an standard example has been used to prove this" -- citation needed. A single example can't prove a claim such as this.
– Raphael
Jun 22, 2016 at 8:08
– Raphael
Jun 22, 2016 at 8:09

The claim is that the intersection of a regular language and a context-free language is context-free. You've intersected a regular language ($$\{ab\}$$) and a context-free language ($$\{a^nb^n\mid n\geq 0\}$$) and the result was a context-free language ($$\{a b\}$$). Sure, that language is also regular but every regular language is also context-free. The statement isn't that the intersection of a regular language and a context-free language is a non-regular context-free language.

Analogously, the child of two mammals is a mammal. You've taken two mammals and you're saying, "Why is their child a cat? It's supposed to be a mammal."

Your mistake is in interpreting the meaning of the statement

The intersection of a regular language and a context-free language is a context-free language.

This statement means that if $R$ is regular and $L$ is context-free then $R \cap L$ is context-free. It doesn't state that $R \cap L$ is not regular; this is just not part of the claim.

Your first example shows that $R \cap L$ could be not regular, but it could also be regular, as your other example shows.

• I don't think this is the issue. Sure, the claim doesn't say that $R\cap L$ is regular. But I think the misunderstanding is that the asker is interpreting "The intersection is context-free" to mean "The intersection is context-free and not regular." Jun 22, 2016 at 7:47
• Thanks Yuval finally able to understand the meaning of the concept. Jun 22, 2016 at 17:38