Regulated rewriting

Regulated rewriting is a specific area of formal languages studying grammatical systems which are able to take some kind of control over the production applied in a derivation step. For this reason, the grammatical systems studied in Regulated Rewriting theory are also called "Grammars with Controlled Derivations". Among such grammars can be noticed:

Matrix Grammars

Basic concepts

Definition
A Matrix Grammar, $MG$, is a four-tuple $G=(N,T,M,S)$ where
1.- $N$ is an alphabet of non-terminal symbols
2.- $T$ is an alphabet of terminal symbols disjoint with $N$
3.- $M=m_1,m_2,...,m_n$ is a finite set of matrices, which are non-empty sequences $m_i=[p_{i_1},...,p_{i_{k(i)}}]$, with $k(i)\ge 1$, and $1\le i\le n$, where each $p_{i_j}1\le j\le k(i)$, is an ordered pair $p_{i_j}=(L,R)$ being $L\in (N\cup T{)}^{*}N(N\cup T{)}^{*},R\in (N\cup T{)}^{*}$ these pairs are called "productions", and are denoted $L\to R$. In these conditions the matrices can be written down as $m_i=[L_{i_1}\to R_{i_1},...,L_{i_{k(i)}}\to R_{i_{k(i)}}]$
4.- S is the start symbol Definition
Let $MG=(N,T,M,S)$ be a matrix grammar and let $P$ the collection of all productions on matrices of $MG$. We said that $MG$ is of type $i$ according to Chomsky's hierarchy with $i=0,1,2,3$, or "increasing length" or "linear" or "without $\lambda$-productions" if and only if the grammar $G=(N,T,P,S)$ has the corresponding property.

The classic example

Note: taken from Abraham 1965, with change of nonterminals names

The context-sensitive language $L(G)=\{a^n{b}^n{c}^n:n\ge 1\}$ is generated by the $CFMG$ $G=(N,T,M,S)$ where $N=\{S,A,B,C\}$ is the non-terminal set, $T=\{a,b,c\}$ is the terminal set, and the set of matrices is defined as $M:$ $[S\to abc]$, $[S\to aAbBcC]$, $[A\to aA,B\to bB,C\to cC]$, $[A\to a,B\to b,C\to c]$.

Time Variant Grammars

Basic concepts
Definition
A Time Variant Grammar is a pair $(G,v)$ where $G=(N,T,P,S)$ is a grammar and $v:\mathbb{\mathbb{N}}\to 2^P$ is a function from the set of natural numbers to the class of subsets of the set of productions.

Programmed Grammars

Basic concepts

Definition

A Programmed Grammar is a pair $(G,s)$ where $G=(N,T,P,S)$ is a grammar and $s,f:P\to 2^P$ are the success and fail functions from the set of productions to the class of subsets of the set of productions.

Grammars with regular control language

Basic concepts

Definition
A Grammar With Regular Control Language, $GWRCL$, is a pair $(G,e)$ where $G=(N,T,P,S)$ is a grammar and $e$ is a regular expression over the alphabet of the set of productions.

A naive example

Consider the CFG $G=(N,T,P,S)$ where $N=\{S,A,B,C\}$ is the non-terminal set, $T=\{a,b,c\}$ is the terminal set, and the productions set is defined as $P=\{p_0,p_1,p_2,p_3,p_4,p_5,p_6\}$ being $p_0=S\to ABC$ $p_1=A\to aA$, $p_2=B\to bB$, $p_3=C\to cC$ $p_4=A\to a$, $p_5=B\to b$, and $p_6=C\to c$. Clearly, $L(G)=\{a^{*}{b}^{*}{c}^{*}\}$. Now, considering the productions set $P$ as an alphabet (since it is a finite set), define the regular expression over $P$: $e=p_0(p_1{p}_2{p}_3{)}^{*}(p_4{p}_5{p}_6)$. Combining the CFG grammar $G$ and the regular expression $e$, we obtain the CFGWRCL $(G,e)=(G,p_0(p_1{p}_2{p}_3{)}^{*}(p_4{p}_5{p}_6))$ which generates the language $L(G)=\{a^n{b}^n{c}^n:n\ge 1\}$. Besides there are other grammars with regulated rewriting, the four cited above are good examples of how to extend context-free grammars with some kind of control mechanism to obtain a Turing machine powerful grammatical device.

References

• Salomaa, Arto (1973) Formal languages. Academic Press, ACM monograph series
• Rozenberg, G.; Salomaa, A. (eds.) 1997, Handbook of formal languages. Berlin; New York : Springer ISBN 3-540-61486-9 (set) (3540604200 : v. 1; 3540606483 : v. 2; 3540606491: v. 3)
• Dassow, Jürgen; Paun, G. 1990, Regulated Rewriting in Formal Language Theory ISBN 0387514147. Springer-Verlag New York, Inc. Secaucus, New Jersey, USA, Pages: 308. Medium: Hardcover.
• Dassow, Jürgen, Grammars with Regulated Rewriting. Lecture in the 5th PhD Program "Formal Languages and Applications", Tarragona, Spain, 2006.
• Abraham, S. 1965. Some questions of language theory, Proceedings of the 1965 International Conference On Computational Linguistics, pp. 1–11, Bonn, Germany,