Ordered Grammar in THEORY OF COMPUTATION [closed]

What is ordered grammar in the theory of computation?

• While this question is not research level and does not give sufficient context, regulated rewriting is an advanced concept beyond the standard CS curriculum. That's why I answered the question. – Hermann Gruber Oct 8 '19 at 8:38
• @HermannGruber indeed a Google search doesn't answer this question so your answer and the question both seem valuable – Bjørn Kjos-Hanssen Oct 11 '19 at 21:06

Ordered grammars are a special case of context-free grammars with regulated rewriting. Another name for context free grammar with regulated rewriting is controlled grammar.

But, what is regulated rewriting? Regulated rewriting alters the "derivation mode" of context-free grammars by adding some control mechanism to the derivation relation. This control mechanism allows for more expressive power than context-free grammars, while maintaining some of the key features, such as a parse tree, which are important e.g. for linguistic applications. Now let us return to ordered grammars.

An ordered grammar is an extension to a context-free grammar $$(N,T,S,P)$$, where the derivation is controlled by a partial order $$\le$$ on the productions. The partial order imposes further constraints on which production rules in $$P$$ can be used to rewrite a nonterminal in $$N$$. For two strings $$xAy$$ and $$xzy$$, with $$A\in N$$ and $$x,y,z \in (N\cup T)^*$$, we say that $$xAy$$ directly derives $$xzy$$ if $$p = A\to z$$ is a production, and if there is no other production $$p' = B \to z'$$ ranked higher in the partial order than $$p$$, where $$B$$ occurs in $$xAy$$.

In complete analogy to the context-free grammars, the relation 'derives' is defined as the transitive closure of the 'directly derives' relation, and the generated language is the set of terminal strings derived from the start symbol $$S$$.

Ordered grammars can generate languages such as {$$a^{2^n} \mid n\ge 0$$}, but they are strictly less expressive than Turing machines.

Definition and examples drawn from: Jürgen Dassow: Grammars with Regulated Rewriting. Tarragona PhD programme, manuscript.