A Reduction of Finitely Expandable Deep Pushdown Automata

Deep Pushdown Automata, Finite Expandability, Reduction, Non-Input Pushdown Symbols

For a positive integer n, n-expandable deep pushdown automata always contain no more than n occurrences of non-input symbols in their pushdowns during any computation. As its main result, the presentation demonstrates that these automata are as powerful as the same automata with only two non-input pushdown symbols---$ and #, where # always appears solely as the pushdown bottom. Moreover, the presentation  demonstrates an infinite hierarchy of language families that follows from this main result. The presentation also points out that if # is the only non-input symbol in these automata, then they characterize the family of regular languages.