A result on the equivalence problem for deterministicpushdown automata

摘要

This paper shows that it is decidable whether or not two deterministic pushdownautomata, one of which is nonsingular (introduced by L. G. Valiant), are equivalent (in the sense that they accept the same languages by empty stack). This is an extension of Valiant's result that the equivalence of two nonsingular deterministic pushdown automata is decidable.