# Ordered Grammar in THEORY OF COMPUTATION [on hold]

What is ordered grammar in the theory of computation?

## put on hold as off-topic by R B, Gamow, Jan Johannsen, Marzio De Biasi, Sasho Nikolovyesterday

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – R B, Gamow, Jan Johannsen, Marzio De Biasi, Sasho Nikolov
If this question can be reworded to fit the rules in the help center, please edit the question.

• 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 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 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.