Does both the language and its complement being context free imply it being deterministic context-free?

77 Views Asked by At

Suppose $L \subset A^*$ is context free and $A^*\setminus L$ is also context free. Does it mean, that $L$ is deterministic context free?

If it is not, I would like to see a counterexample (I failed to construct one myself).

Note that the converse is true. Moreover, a complement to a deterministic context free language is also deterministic context free as one can simply change labels on the corresponding deterministic pushdown automaton.

1

There are 1 best solutions below

0
On BEST ANSWER

No, as shown in this answer and this one on cs.stackexchange. You cannot even conclude that your language is unambiguous, as shown in this answer.