0
$\begingroup$

I know that intersection of CFL and regular language is CFL and hence CFL is closed if one of the languages is regular. One of the most common examples to show this is regular language being $p^*q^*$ and CFL being $p^n q^n$.

Now if I promote regular language to CFL according to Chomsky hierarchy as all regular languages are context free languages, then the question changes to CFL intersection CFL which is not closed and hence we cannot say that the resultant language is surely a "CFL".

Why are the results different using both the methods?

$\endgroup$
  • $\begingroup$ When we say that "intersection of two CFLs is not necessarily a CFL" we mean "any two CFLs". When we talk about Regular languages we mean a special subclass of CFLs. You can rephrase it as "intersection of any CFL and a CFL from a special subsclass (Regular languages) is CFL". $\endgroup$ – fade2black Jul 14 '17 at 18:58
  • 1
    $\begingroup$ Something like this. You have two sets $N$ (all natural numbers) and $E$ (all natural even numbers). It is true that if $a \in N$ and $b \in E$ then $ab$ is always an even number. However, you cannot say that for the set $N$ and any set $A$, in particular if $A$ is a set of odd natural numbers. $\endgroup$ – fade2black Jul 14 '17 at 19:11
  • 2
    $\begingroup$ I don't really understand the question. Context-free languages are closed under intersection with regular languages, but not under intersection with context-free languages. This doesn't mean that the intersection of any two context-free languages is necessarily not context-free. Rather, it means quite the opposite – that the intersection of two context-free languages is not necessarily context-free. $\endgroup$ – Yuval Filmus Jul 14 '17 at 19:52
  • 1
    $\begingroup$ If all you know about two languages is that they are context-free, then you cannot conclude anything about the context-freeness of their intersection. If you know that one of them is moreover regular, then you can conclude that the intersection is context-free. In general, when you know more information, you can conclude more. $\endgroup$ – Yuval Filmus Jul 14 '17 at 19:53
  • 1
    $\begingroup$ "I know that intersection of CFL and regular language is CFL and hence CFL is closed if one of the languages is regular. " -- you need to be more precise about when you are talking about the two classes, and when about elements from the classes. $\endgroup$ – Raphael Jul 14 '17 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.