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?

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

2 Answers 2

Reset to default
10
$\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."

Improve this answer
$\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.

Improve this answer
$\endgroup$
2
  • $\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, 2016 at 7:47
  • $\begingroup$ Thanks Yuval finally able to understand the meaning of the concept. $\endgroup$
    – Shaji Thorn Blue
    Jun 22, 2016 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.