The usual candidates for context free languages whose complement is also context free, but they are not regular are the Deterministic Context Free Languages ($DCFL$).

For example, $L=\{a^nb^n\mid n\in\mathbb N\}$ is such language.

Is there a language, $L\in CFL\setminus DCFL$ such that $\bar L\in CFL$?

Since $DCFL$ is closed under complement, this is equivalent of asking whether $$CFL\cap co\text{-}CFL = DCFL$$


1 Answer 1


See here:

For every finite, non-unary alphabet, the language of all palindromes is not in DCFL, but in the intersection of coCFL and CFL.


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.