ON THE DECIDABILITY OF EQUIVALENCE FOR DETERMINISTIC PUSHDOWN AUTOMATA.

L. G. Valiant has shown that for a subclass N//0 of empty-stack accepting DPDA without epsilon -operation, the equivalence can be decided between automata in N//0. The class of languages accepted by automata in this N//0 properly contains the class of LL(k) languages. Harrison and others have shown that the equivalence can be decided between an empty-stack accepting DPDA with general epsilon -operation (this class is referred to as D//0) and a simple deterministic language. This paper extends these results so that both the above results are integrated and shows that the equivalence can be decided between a DPDA in D//0 and a DPDA in N//0.