Prefix pushdown automata and their simplification

Abstract

A prefix pushdown automatonM, accepts a wordx, with respect to a languageZ, if and only if M makes a sequence of moves so it reads xy, for some y∊Z, and enters a final state. This paper demonstrates that for every recursively enumerable languageL, there exist a linear languageZ, and a prefix pushdown automatonM, 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

Keywords:

• Pushdown automata
• linear languages
• recursively enumerable languages
• descriptional complexity