HiveBrain v1.2.0
Get Started
← Back to all entries
snippetModerate

How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
cflscanthehowcflproperregregsintersectionand

Problem

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 ?

Solution

You are confusing two different statements.

  • $\mathrm{CFL} \cap \mathrm{REG} = \mathrm{REG}$ or, equivalently,



for all $L_1 \in \mathrm{REG}$ : $L_1 \in \mathrm{CFL}$.

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

Context

StackExchange Computer Science Q#84903, answer score: 11

Revisions (0)

No revisions yet.