NESA
Ginsburg, Greibach, and Harrison [1] have recently proposed a mathematical model for modern compilers which they claim abstracts the essential structure of the compilation process. Their basic model, called a stack automaton (SA) consists of an input tape with end markers, a finite state control, and a stack (Fig. 1). The input head maybe moved either right or left. The stack is similar to a push-down store, and may be modified by erasing symbols from the top or adding symbols at the top. Unlike a push-down store, however, the SA is also allowed to move its stack head into the stack in a read-only mode. In [1] it is shown that every context-sensitive language is accepted by a deterministic SA. Furthermore, it is shown every set accepted by some SA is recursive.
A stack automaton is called nonerasing if no symbol may be erased from the stack.
(1) The deterministic, nonerasing stack automaton is equivalent to the deterministic -bounded Turing machine.
(2) The nondeterministic, nonerasing stack automaton is equivalent to the nondeterministic -bounded Turing machine.