3
$\begingroup$

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

In fact, a PDA 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.

$\endgroup$
1
$\begingroup$

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.

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)

Reference

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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