2SA
Two-way nondeterministc stack automata. Other names: 2NSA.
The stack automaton is an abstract machine (represented in Figure 1) consisting of a two-way input tape with endmarkers, a finite-state control, and a pushdown list which can be entered in a read-only mode. The pushdown list, or stack, is a semiinfinite tape which will always hold a finite length string of nonblank symbols to the left of an infinite sequence of blanks. The cell of the leftmost blank is called the top of the stack. A move of the automaton depends upon the state of the finite control, the input symbol scanned, and the stack symbol scanned. In one move the stack automaton can change state and move its input head one cell left or right or leave it stationary.