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 Nikolov yesterday

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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Hermann Gruber Oct 8 at 8:38
  • 1
    $\begingroup$ @HermannGruber indeed a Google search doesn't answer this question so your answer and the question both seem valuable $\endgroup$ – Bjørn Kjos-Hanssen Oct 11 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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.