Direct or cascade product of pushdown automata

摘要

The direct or cascade product of pushdown automata is discussed and the relation to other types of machines is clarified. The main results are follows. (1) The direct product of k pushdown automata, where k is greater than one but finite, is more powerful than a pushdown automaton and less powerful than a linear bounded automaton. (2) The cascade product of two pushdown automata is equivalent to a turing machine.