patternMinor
Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?
Viewed 0 times
theequivalentfreearelanguageslanguagerecognizedonedeterministicmachines
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#110984, answer score: 3
Revisions (0)
No revisions yet.