Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
Sheila A. Greibach · SIAM Journal on Computing · 1974
A jump pushdown store acceptor can in one step erase its store through the first occurrence of one of its pushdown store symbols. Every deterministic context-free language can be accepted by a deterministic jump pushdown store acceptor operating with finite delay (semirealtime). For deterministic jump pushdown store acceptors operating with finite delay, $n + 1$ types of pushdown store symbols are more powerful than n types of pushdown store symbols. As a consequence, it can be shown that the family of deterministic context-free languages does not form a principal AFDL.