<p>Ordered grammars are a special case of context-free grammars with regulated rewriting. Another name for context free grammar with regulated rewriting is <a href="https://en.wikipedia.org/wiki/Controlled_grammar" rel="nofollow noreferrer">controlled grammar</a>. </p>

<p>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. </p>

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

<p>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 <span class="math-container">$S$</span>. </p>

<p>Ordered grammars can generate languages such as {<span class="math-container">$a^{2^n} \mid n\ge 0$</span>}, but they are strictly less 
expressive than Turing machines.</p>

<p>Definition and examples drawn from:
Jürgen Dassow: <a href="http://theo.cs.ovgu.de/dassow/tarraphd.pdf" rel="nofollow noreferrer">Grammars with Regulated Rewriting</a>. Tarragona PhD programme, manuscript.</p>

CC BY-SA 4.0
2019-10-07T20:08:19.280Z
2019-10-11T20:26:31.250Z
2019-10-11T20:26:31.250Z
Hermann Gruber
<p>What is ordered grammar in the theory of computation? </p>

CC BY-SA 4.0
2019-10-08T08:38:02.773Z
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
CC BY-SA 4.0
2019-10-11T21:06:12.660Z
@HermannGruber indeed a Google search doesn't answer this question so your answer and the question both seem valuable
Bjørn Kjos-Hanssen
<fl.formal-languages><grammars>
Ordered Grammar in THEORY OF COMPUTATION
Raj Aryan Pathak
# Ordered Grammar in THEORY OF COMPUTATION

(Asked by: username_0 on 2019-10-07)

What is ordered grammar in the theory of computation?

**Tags:** fl.formal-languages, grammars
> **Comments:**
> **username_1**: 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.  
> **username_2**: @HermannGruber indeed a Google search doesn't answer this question so your answer and the question both seem valuable  

---

## 1 answers

### Answer by username_1 on 2019-10-07. Score: 5

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](https://en.wikipedia.org/wiki/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](http://theo.cs.ovgu.de/dassow/tarraphd.pdf). Tarragona PhD programme, manuscript.


---

