0
$\begingroup$

Is CFL $\cap$ DCFL = CFL, always true?

CFL - Any Context Free Language

DCFL - Any Deterministic Context Free Language

$\endgroup$
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$
    – Arno
    Commented Nov 19, 2022 at 12:03

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.