Sets accepted by one-way stack automata are context sensitive
- Hopcroft, J.E.
- Ullman, J.D.
Publication date
August 1968
DOI Publisher
Published by Elsevier Inc. ISSN
0019-9958Abstract
A stack automaton is a pushdown automaton that can read the interior of its pushdown list without altering it.It is shown that a nondeterministic stack automation with a one-way input tape can be simulated by a deterministic linear bounded automaton. Hence, each nondeterministic one-way stack language is context sensitive
Add to ORKG