On restricted context-free grammars (Q414885)

The contribution investigates the generative power of several derivation-restricted context-free grammars. Many derivation restriction mechanisms for context-free grammars have already been studied in the literature, and the current contribution investigates a restriction on the non-terminals that allows/disallows the application of a production depending on the presence/absence of certain symbols in the sentential form. Context-free grammars using such restrictions on the derivations are shown to be equivalent in generative power to random context grammars [\textit{S. Ewert} and \textit{A. van der Walt}, ``The power and limitations of random context'', Top. Comput. Math. 9, 33--43 (2003; Zbl 1102.68619)]. While this equivalence is also true for the permitting variants (in which only the presence of symbols can be required), it remains an open question whether this is also true in the presence of forbidding context. With the equivalence established, the generative power for most classes is presented in some simple hierarchies. The equivalence is also used to derive new normal forms for random context grammars. It is even demonstrated that the obtained normal forms are as simple as possible (in a rather restricted sense). This is achieved by demonstrating that further restrictions to the context indeed limit the generative power. At last, the contribution investigates a minor twist on the previous model. Instead of non-terminals, productions can now force the presence/absence of terminal symbols in the sentential form. The main line of research is repeated for this model (with different arguments) to show that the non-erasing variant of this model characterizes exactly the context-sensitive languages. As before, the equivalence is used to derive a new normal form for this model. The contribution is expertly written and the main points can be understood on the first reading. However, it is very technical in the mathematical development. While the main notions are understandable also to non-expert readers, I would recommend an introduction to regulated rewriting or derivation-restricted context-free grammars to non-expert readers. On the positive side, the contribution re-uses its results efficiently, which is enjoyable to read and allows the reader to focus on the actual differences.