{\langle p_4,0 \rangle} $. Thus, by setting $ (s_2,p_3) $ as the only accepting state, we can obtain the desired machine.

Next, we prove that the language $ {\mathtt{END}}$ is recognized neither by 1-way deterministic pushdown automata (1DPAs) nor by realtime deterministic $k$-counter automata (realtime DkCAs)[^3]. For this purpose, we introduce the following lemma (the pumping lemma for deterministic context-free languages (DCFLs)) [@Yu89].

\[lemma:pumping\] (Pumping Lemma for DCFLs [@Yu89]) Let $ L $ be a DCFL. Then there exists a constant $ C $ for $ L $ such that for any pair of words $ w $, $ w' \in L $ if

1.  $ w = xy $ and $ w' = xz, |x| > C $, and

2.  $ ^{(1)}y = \,^{(1)}z $, where $ ^{(1)}w $ is defined to be the first symbol of $ w $ $$^{(1)}w = \left \{ 
            \begin{array}{ll}
            x & \mbox{ if } |w| > 1, w=xy, \mbox{ and } |x| = 1;\\
            w & \mbox{ if } |w| \leq 1,
            \end{array}\right .$$

then either (3) or (4) is true:

3.  there is a factorization $ x=x_1 x_2 x_3 x_4 x_5, |x_2 x_4| \geq 1 $ and $ |x_2 x_3 x_4| \leq 