[Solved]: Is intersection of regular language and context free language is "always" context free language

Problem Detail: 

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?

Asked By : Shaji Thorn Blue

Answered By : David Richerby

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."

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59886

3.2K people like this

 Download Related Notes/Documents