1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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