A note on limited pushdown alphabets in stateless deterministic pushdown automata (Q2856007)

It is well known that there exists an infinite hierarchy of classes of deterministic context-free languages based on the number of states that are necessary to characterize them by deterministic pushdown automata (unlike in the general case: for any context-free language, a stateless pushdown automaton can be constructed). Recently, \textit{A. Meduna} et al. [Lect. Notes Comput. Sci. 7386, 236--243 (2012; Zbl 1304.68113)] established an infinite hierarchy of languages also on the ``lowest level'' of the state hierarchy based on the number of pushdown symbols: They showed the existence of languages accepted by stateless deterministic pushdown automata with \(n\) pushdown symbols that cannot be accepted by the same type of automata with \(n-1\) pushdown symbols. This paper improves this result by reducing the size of the alphabet of the witness languages from \(2n\) to \(2\), which is the best possible improvement, as unary languages of these automata can be singleton sets only. The result is also generalized to the other levels of the state hierarchy in the case of real-time pushdown automata (deterministic pushdown automata with no \(\varepsilon\)-transitions): For any \(m\), \(n\), there are binary languages accepted by \(m\)-state real-time pushdown automata with \(n\) pushdown symbols that cannot be accepted by \(m\)-state realtime automata with \(n-1\) pushdown symbols. The question whether this result also holds in the case of \(m\)-state deterministic pushdown automata with \(\varepsilon\) transitions, remains open.