Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?

Question

In Introduction to Automata Theory, Languages, and Computation, John Hopcroft mentioned[1]

In fact the languages of one counter machines are accepted by deterministic PDA's although the proof is surprisingly complex.

How to prove that?

In contrast, is there a language that is accepted by some DPDA but can't be accepted by any non-deterministic one counter machines?

Reference

[1]: John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. Boston/MA: Addison Wesley. P359.

Answer 1

The conclusion is: the languages recognized by DOCA(deterministic one counter automata) is a proper subset of the languages recognized by DPDA(deterministic pushdown automata).

---

The reason why Hopcroft said the proof is complex is that in his definition, the input string of DOCA is appended with an endmarker \$ [1:P356]. So, the actual difficulty is to prove that: for any language $L$, there exists DPDA $P$ s.t. $L = L(P)$ $\Leftrightarrow$ there exists DPDA $P$ s.t. $L\$ = L(P)$.

This is shown in Exercise 8.5.2 [1:P362] .But I failed to prove the exercise by Hopcroft's hint. I find a detailed proof here by Hendrik Jan Hoogeboom and Joost Engelfriet [2, see remark end of Section 1.6].

Since, we can prove that the languages of DOCA is a subset of the languages of DPDA.

---

In contrast, $\{ a^n b^m a^m b^m | n, m \ge 1 \}$ is a language that can be recognized by some DPDA but can't be recognized by any DOCA. (Thanks to @Vor in his answer)

References

[1] John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. Boston/MA: Addison Wesley.

[2] H.J. Hoogeboom, J. Engelfriet (2004). Pushdown Automata. Chapter in: Formal Languages and Applications, C. Martín-Vide, V. Mitrana, G. Paun, eds. Springer.