Quasi-rocking real-time pushdown automata

摘要

A pushdown automaton (PDA) is quasi-rocking if it preserves the stack height for no more than a bounded number of consecutive moves. Every PDA can be transformed into an equivalent one that is quasi-rocking and real-time and every finite-turn (one-turn) PDA can be transformed into an equivalent one that is quasi-rocking or real-time. The quasi-rocking [quasi-rocking in the increasing mode, and quasi-rocking in the decreasing mode] real-time restriction in finite-turn (one-turn) PDAs coincides with the double Greibach [reverse Greibach, and Greibach] form in nonterminal-bounded (linear) context-free grammars. This provides complete grammatical characterizations of quasi-rocking and/or real-time (finite-turn and one-turn) PDAs and, together with known relations and other relations proved in the present paper, yields an extended hierarchy of PDA languages. Basic decision properties for PDAs can be stated in stronger forms by using the quasi-rocking and real-time restrictions and their undecidability/decidability status rests on the way PDAs quasirock.