1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ cs.stackexchange.com/questions/18642/… $\endgroup$ – D.W. Jun 22 '16 at 7:04
  • 4
    $\begingroup$ "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. $\endgroup$ – Raphael Jun 22 '16 at 8:08
  • 1
    $\begingroup$ You already give yourself the answer, so I don't understand what you are asking. $\endgroup$ – Raphael Jun 22 '16 at 8:09
9
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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." $\endgroup$ – David Richerby Jun 22 '16 at 7:47
  • $\begingroup$ Thanks Yuval finally able to understand the meaning of the concept. $\endgroup$ – Shaji Thorn Blue Jun 22 '16 at 17:38

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.