$ can have only 0s. Thus, for any factorization $ w = x_1 x_2 x_3 y_1 y_2 y_3 $, $ x_1 x_2^i x_3 y_1 y_2^i y_3 \not\in {\mathtt{END}}$ for $ i \neq 1 $. Thus, (4) does not hold. This is a contradiction. Therefore, $ {\mathtt{END}}$ is not a DCFL, which implies no 1DPA can recognize $ {\mathtt{END}}$.

\[theorem:impossibilityDkCA\] The language $ {\mathtt{END}}$ cannot be recognized by any realtime DkCA.

We assume that there exists a realtime DkCA that recognizes $ {\mathtt{END}}$. We consider an input of the form $ w = 2^m x y (x\in \{0,1\}^m, y\in \{0,1\}^*) $. Then we have $ 2^m $ possible $ x $’s. For any $ x_1 $ and $ x_2 \in \{0,1\}^m (x_1 \neq x_2) $, we will show that there exists a $ y $ such that $ 2^m x_1 y \in {\mathtt{END}}$ and $ 2^m x_2 y \not\in {\mathtt{END}}$ or vice versa.

We assume that $ x_1[i] \neq x_2[i] $. Note that there exists such an $ i $ since $ x_1 \neq x_2 $. We also assume that $ x_1[i] = 1 $ and $ x_2[i] = 0 $ without loss of generality. We set $ y=0^{i-1} $. Then 