# Show that this language cannot be accepted by a deterministic push-down automaton [duplicate]

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

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

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.