An Automata-Theoretic Characterization of the Chomsky-Hierarchy

摘要

In this paper a new family of stateless (non-deterministic) pushdown automata are used to accept languages of the Chomsky hierarchy. Having only a stack with at most 1 symbol the regular languages can be recognized. The usual pushdown automata accept the context-free languages. The extended version which uses additional half-translucent shadow symbols accept the context-sensitive languages. Finally, allowing a kind of A-transitions the automata accept any recursively enumerable languages.