2
$\begingroup$

How do you show that there exists no DPDA that accepts $ L = \{0^n1^n \} \cup \{ 0^n1^{2n}\}$ ?

$\endgroup$

marked as duplicate by Tara B, Amzoti, Davide Giraudo, Brian M. Scott, Dominic Michaelis Apr 12 '13 at 21:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Do you know any techniques for showing a language can't be accepted by a DPDA? $\endgroup$ – Tara B Apr 6 '13 at 20:00
2
$\begingroup$

I copy rather verbatim my answer at cs.stackexchange

The most obvious (and not-at-all complicated) proof method for showing languages not deterministic-context-free is the fact that DCFL is closed under complement, whereas CFL is not.

There are similar arguments, also related to the fact that on an input string a DPDA has (at most) one computation (ignoring possible sequences of lambda transitions at the end). As an example, $\{ a^nb^m \mid n\ge 1, m=n \mbox{ or } m=2n \}$ is not DCFL; which is seen as follows.

Assume it is. Consider a computation of its DPDA $\cal A$ on input $a^nb^{2n}$. As $a^nb^n$ belongs to the language, the computation must enter a final state halfway the $b$'s. Now rewrite $\cal A$ such that from the first final state entered we move to a copy of $\cal A$ where all letters $b$ are changed into $c$. Only keep final states in this copy that are reached after reading at least one $c$. Then the new automaton will accept $\{ a^nb^nc^n \mid n\ge 1 \}$, which (we know) is not context-free. Contradiction, $\cal A$ cannot exist.

$\endgroup$

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