snippetModerate
How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL?
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 ?
Am I interpreting Chomsky diagram wrongly ?
Solution
You are confusing two different statements.
for all $L_1 \in \mathrm{REG}$ : $L_1 \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.
- $\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.