Is CFL $\cap$ DCFL = CFL, always true?
CFL - Any Context Free Language
DCFL - Any Deterministic Context Free Language
1
-
$\begingroup$ Your notation is off. $\mathrm{CFL} \cap \mathrm{DCFL}$ would denote the class of languages which are both context-free and deterministic context free. $\endgroup$– ArnoNov 19, 2022 at 12:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Even the intersection of two deterministic context-free languages may not be context-free.
Consider $L_1 = \{a^nb^nc^m\mid n,m\geqslant 0\}$ and $L_2 = \{a^nb^mc^m\mid n,m\geqslant 0\}$. Both languages are DCFL, but their intersection is $\{a^nb^nc^n\mid n\geqslant 0\}$ which is not context-free.
answered Nov 19, 2022 at 12:02