Two results concerning the power of two-way deterministic Pushdown Automata
Daniel Paul Martin, John Gwynn · 1973
It is known that there is no one-way, non-deterministic Pushdown Automaton (INPDA) which is a universal machine for the class of Finite Automata [6]. We will show that there is a two-way, deterministic Pushdown Automaton (2DPDA), U, which is a universal machine for the class of Finite Automata (FA). Our method will parallel Knuth and Bigelow's construction of a language which is not context sensitive but which is the acceptance set of some stack automaton [5], that is, we will construct a language which is not context-free, but which is accepted by a 2DPDA.