# 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

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.