A stack automaton is a pushdown automaton with the added privilege of scanning the contents of its pushdown tape without erasing. In this paper, the deterministic stack automaton with a one-way input (dsa) is considered.
It is shown that if L is a language accepted by a dsa and R is a regular set, then L/R = {w ] for some x in R, wx is in L} is accepted by a dsa. As a corollary, end markers are not needed on the input of the dsa. It is also shown that if L is accepted by a dsa, then Max(L) = {w ] w in L and for no x is wx in L} is accepted by a dsa.
I. I NTRODUCTI ON
The stack automaton has been studied as an abstract recognition device
The general device is nondeterministic, has a two-way input with end markers, a finite control and a pushdown store called the stack. Unlike a pushdown automaton, however, the stack automaton can cause its head to leave the top of the pushdown store and scan the stack in a read-only mode. This paper is concerned with deterministic one-way stack automata.
The study of operations on families of languages has proven important in the theory of languages. Many of the closure properties of (deterministic) one-way pushdown automata have been established for (deterministic) one-way stack automata [2]. In particular, the family of languages accepted by one-way stack automata has been shown to be closed under union, intersection with a regular set, concatenation, Kleene closure, generalized sequential machine mappings and quotient with a regular set. (If L 1 and L~ are languages, then the quotient of L1 with L2, denoted L1/L 2 , is the set 1