Non-Self-Embedding Grammars, Constant Height Pushdown Automata, and Limited Automata

Overview & Synopsis

Non-self-embedding grammars are a restriction of contextfree grammars which does not allow to describe recursive structures and, hence, which characterizes only the class of regular languages. A double exponential gap in size between non-self-embedding grammars and deterministic finite automata is known. The same size gap is also known from constant height pushdown automata and 1-limited automata to equivalent deterministic finite automata. Constant height pushdown automata and 1-limited automata are compared with non-self-embedding grammars. It is proved that non-self-embedding grammars and constant height pushdown automata are polynomially related in size. However, they can be exponentially larger than 1-limited automata.