5
$\begingroup$

Intersection of CFL and regular is always CFL. But according to Chomsky hierarchy diagram, regular languages lie completely inside CFL. So, as regular set is completely inside CFL set, their intersection should be regular right ?

Am I interpreting Chomsky diagram wrongly ?

$\endgroup$
9
$\begingroup$

No, you are misinterpreting stuff.

The set of languages (DFL, regular, ...) and the set of strings in a language are independent.

It is entirely possible that a regular language contains strings that are not inside a Context free language.

The trivial example is where the regular language is all strings $\Sigma^*$ and the CFL is any other language. The intersection between them is the original CFL.

$\endgroup$
  • 1
    $\begingroup$ In this diagram encrypted-tbn3.gstatic.com/…. Regular language is subset of CFL. So according to subset property of sets , any set's intersection with it's subset is the subset itself right (which is regular) ? $\endgroup$ – Rajesh R Dec 4 '17 at 15:06
  • 7
    $\begingroup$ But each language is a set of strings so when talking about the intersection between 2 languages you are talking about intersecting the set of strings. That is independent from the set of languages. $\endgroup$ – ratchet freak Dec 4 '17 at 15:18
  • $\begingroup$ Ok so Chomsky hierarchy says intersection of set of all CFL's and set of all Regular languages is set of regular languages right? $\endgroup$ – Rajesh R Dec 4 '17 at 15:50
12
$\begingroup$

You are confusing two different statements.

  1. $\mathrm{CFL} \cap \mathrm{REG} = \mathrm{REG}$ or, equivalently,
    for all $L_1 \in \mathrm{REG}$ : $L_1 \in \mathrm{CFL}$.
  2. For all $L_1 \in \mathrm{REG}$, $L_2 \in \mathrm{CFL}$ : $L_1 \cap L_2 \in \mathrm{CFL}$.

The first makes a statement on two sets of languages (aka language classes), the second makes one over (many) pairs of sets of strings (aka languages). So in mixing the two, you are creating a type error.

Also, you seem to suggest that if a language is context-free, it's not regular. That is false; we have $\mathrm{REG} \subsetneq \mathrm{CFL}$ (cf. 1.), so showing a language is CFL (using 2.) does not preclude it from being regular. Specifically, it's easy to find examples of a non-regular context-free and a regular language whose intersection is regular.

$\endgroup$
  • $\begingroup$ Very clear distinction between the two statements, but which one is correct? (I know they're not mutually exclusive, but if I understood the other answer correctly, only one of them happens to be true.) $\endgroup$ – Wildcard Dec 4 '17 at 16:17
  • 2
    $\begingroup$ Both are true. The false one is $\forall L_1 \in REG, L_2 \in CFL: L_1 \cap L_2 \in REG$. $\endgroup$ – reinierpost Dec 4 '17 at 16:45

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.