# 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)\geq 1$, and $1\leq i\leq n$, where each $p_{i_{j}}1\leq j\leq 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\rightarrow R$. In these conditions the matrices can be written down as $m_{i}=[L_{i_{1}}\rightarrow R_{i_{1}},...,L_{i_{k(i)}}\rightarrow 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\geq 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:$ $\left[S\rightarrow abc\right]$, $\left[S\rightarrow aAbBcC\right]$, $\left[A\rightarrow aA,B\rightarrow bB,C\rightarrow cC\right]$, $\left[A\rightarrow a,B\rightarrow b,C\rightarrow c\right]$.

## 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 {N} \rightarrow 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\rightarrow 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\rightarrow ABC$ $p_{1}=A\rightarrow aA$, $p_{2}=B\rightarrow bB$, $p_{3}=C\rightarrow cC$ $p_{4}=A\rightarrow a$, $p_{5}=B\rightarrow b$, and $p_{6}=C\rightarrow 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\geq 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.