Publication Details
Prefix Pushdown Automata
prefix pushdown automata, pushdown, recursively enumerable languages
The present paper demonstrates this result for some simplified versions of prefix pushdown automata. Finally, it discusses the descriptional complexity of these automata.
A prefix pushdown automaton, M, accepts a word, x, with respect to a language, Z, if and only if M makes a sequence of moves so it reads xy, for some y \in Z, and enters a final state. This paper demonstrates that for every recursively enumerable language, L, there exist a linear language, Z, and a prefix pushdown automaton, M, so that L equals the prefix language that M accepts with respect to Z. Besides the acceptance by final state, this result is established in terms of acceptance by empty pushdown and acceptance by final state and empty pushdown. In addition, the present paper demonstrates this result for some simplified versions of prefix pushdown automata. Finally, it discusses the descriptional complexity of these automata.
@article{BUT191795,
author="Alexandr {Meduna}",
title="Prefix Pushdown Automata",
journal="International Journal of Computer Mathematics",
year="1999",
volume="1999",
number="71",
pages="1--20",
issn="0020-7160"
}