Deterministic stack automata and the quotient operator

摘要

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 is wx in L} is accepted by a dsa.