patternMinor
Is there $L$ such that $L$ and $\bar L$ are context free, but $L$ is not deterministic context free?
Viewed 0 times
suchbarfreearebutthatcontextdeterministicandthere
Problem
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$$
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$$
Solution
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.
For every finite, non-unary alphabet, the language of all palindromes is not in DCFL, but in the intersection of coCFL and CFL.
Context
StackExchange Computer Science Q#37412, answer score: 3
Revisions (0)
No revisions yet.