1—Way stack automaton with jumps

摘要

Deterministic 1-way stack automata (SA) are generalized to include jumps, and it is established that for any SA there exists an equivalent semi-real-time Jump SA. Applying a well-known information theoretic argument to the Jump SA, we prove that certain languages cannot be SA languages. Parallel to Cole's treatment (J. Assoc. Comput. Mach. (1971), 306–328) of pushdown automata, we show that SA's can be reduced to real-time n-dimensional cellular automata.