Accepting Grammars and Systems via Context Condition Grammars
Henning Bordihn, Henning Fernau · Journal of automata, languages and combinatorics · 1996
We investigate several kinds of regulated rewriting (matrix, ordered, programmed, and variants thereof) and of parallel rewriting mechanisms (Lindenmayer systems, uniformly limited Lindenmayer systems, limited Lindenmayer systems and scattered context grammars) as accepting devices, in contrast with the usual generating mode. In a lot of cases, accepting mode turns out to be exactly as powerful as generating mode. These equivalences can be proved using a theorem on so-called context condition grammars. Interestingly, accepting devices are (strictly) more powerful than their generating counterparts in case of non-erasing ordered, programmed, and matrix grammars with appearance checking (even programmed grammars with unconditional transfer), and 1lEPT0L systems, where we arrive at new characterizations of the context-sensitive languages. If we admit erasing productions, we get new characterizations of the recursively enumerable languages. Moreover, we supplement some hierarchies presented in [7], [10], and [31].