Regularity and Related Problems for Deterministic Pushdown Automata
Leslie Gabriel Valiant · Journal of the ACM · 1975
It ~S shown that to decide whether the language accepted by an arbitrary deterministic pushdown automaton is LL (k), or whether ~t m accepted by some one-counter or finite-turn pushdown machine, must be at least as difficult as to decide whether it is regular.The regularity problem itself is analyzed in detail, and Stearns' dec~mon procedure for this as improved by one level of exponentiatlon Upper bounds, close to known lower bounds, are obtained for the succinctness with which a pushdown automaton, and various restrictions of it, can express equivalent fimte-state machines