Equivalence of deterministic pushdown automata revisited

This paper briefly analyzes main ideas underlying the comparison algorithm that made it possible to prove the equivalence of deterministic pushdown automata. An example of using this algorithm is presented. The relationship of this algorithm with other results in this area is shown. Moreover, the decidability of problems associated with some classes of formal grammars is established. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 24–39, March–April 2007.