Some results on subclass containment problems for special classes of dpda's related to nonsingular machines (Q1060563)

The results of this paper are concerned with the equivalence problem and the subclass containment problem for deterministic pushdown automata (dpda). The class of weakly nonsingular dpda's which includes the class of nonsingular dpda's is defined. It is shown that it is undecidable whether a dpda is weakly nonsingular and whether a dpda accepts a weakly nonsingular language. As a corollary, the negative solution of the problem to decide whether a dpda is nonsingular is given. Next, the class of super-nonsingular dpda is introduced, a subclass of weakly nonsingular dpda's, and it is shown that it is decidable whether a dpda is super- nonsingular and whether a dpda accepts a super-nonsingular language. Finally is is observed that the (open) problem of deciding whether a dpda accepts an LL(k) language reduces to the problem of deciding whether a super-nonsingular dpda accepts an LL(k) language.