Some results on subclass containment problems for special classes of DPDA'S related to nonsingular machines

A content-free language is said to be weakly (w-)nonsingular if it is accepted by a nonsingular deterministic pushdown automaton in the sense of Oyamaguchi, Inagaki and Honda (1980). It is undecidable whether a deterministic pushdown automaton (dpda) accepts a w-nonsingular language and whether a dpda is nonsingular in the sense of Valiant (1973). Next, the class of super-nonsingular dpda's (which is a subclass of w-nonsingular dpda's) is introduced. It is decidable whether a dpda is super-nonsingular and whether a dpda accepts a super-nonsingular language. As a consequence, the 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.