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 $T$
3.- $M\; =\; \{m\_1,\; m\_2,...,\; m\_n\}$ is a finite set of matrices, which are non-empty sequences $m\_\{i\}\; =\; [p\_\{i\},...,p\_\{i\_\{k(i)]$, with $k(i)geq\; 1$, and$1\; leq\; i\; leq\; n$, where each $p\_\{i\_\{j\; 1leq\; jleq\; k(i)$, is an ordered pair$p\_\{i\_\{j\; =\; (L,\; R)$being$L\; in\; (N\; cup\; T)^*N(Ncup\; T)^*,\; R\; in\; (Ncup\; T)^*$these pairs are called "productions", and are denoted$L\; ightarrow\; R$. In these conditions the matrices can be written down as$m\_i\; =\; [L\_\{i\_\{1\; ightarrow\; R\_\{i\_\{1,...,L\_\{i\_\{k(i)\; ightarrow\; 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 classical example (taked from [5] with change of nonterminals names)

The context-sensitive language $L(G)\; =\; \{\; a^nb^nc^n\; :\; ngeq\; 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\; ightarrow\; abc\; ight]$,$left\; [S\; ightarrow\; aAbBcC\; ight]$,$left\; [A\; ightarrow\; aA,B\; ightarrow\; bB,C\; ightarrow\; cC\; ight]$,$left\; [A\; ightarrow\; a,B\; ightarrow\; b,C\; ightarrow\; c\; ight]$.

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\}\; ightarrow\; 2^\{P\}$ is a function from the set of naturalnumbers to the class of subsets of the set the 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\; ightarrow\; 2^\{P\}$ are the "success" and "fail" functions from the set of productionsto the class of subsets of the set the 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 the 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\; ightarrow\; ABC$$p\_1\; =\; A\; ightarrow\; aA$,$p\_2\; =\; B\; ightarrow\; bB$,$p\_3\; =\; C\; ightarrow\; cC$$p\_4\; =\; A\; ightarrow\; a$,$p\_5\; =\; B\; ightarrow\; b$, and$p\_6\; =\; C\; ightarrow\; 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\_1p\_2p\_3)^*(p\_4p\_5p\_6)$.

Combining the CFG grammar $G$ and the regular expression$e$, we obtain the CFGWRCL $(G,e)=(G,p\_0(p\_1p\_2p\_3)^*(p\_4p\_5p\_6))$which generates the language$L(G)\; =\; \{\; a^nb^nc^n\; :\; ngeq\; 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.

Sources

[1] Salomaa, Arto Formal languagesAcademic Press, 1973 ACM monograph series

[2] G. Rozenberg, A. Salomaa, (eds.)Handbook of formal languagesBerlin; New York : Springer, 1997 ISBN 3540614869 (set) (3540604200 : v. 1; 3540606483 : v. 2; 3540606491: v. 3)

[3] Regulated Rewriting in Formal Language TheoryJurgen Dassow; G. PaunPages: 308. Medium: Hardcover. Year of Publication: 1990 ISBN:0387514147. Springer-Verlag New York, Inc. Secaucus, NJ, USA

[4] Grammars with Regulated RewritingJurgen Dassow Otto-von-GuerickeAvailable at: [http://citeseer.ist.psu.edu/700926.html] and [http://theo.cs.uni-magdeburg.de/dassow_eng.html] ( [http://theo.cs.uni-magdeburg.de/dassow/tarraphd.pdf] )

[5] Some questions of language theory S. Abrahamin Proceedings of the 1965 International Conference On Computational Linguisticspp 1 - 11, Bonn, Germany Year of Publication: 1965Available at: [http://acl.ldc.upenn.edu/C/C65/C65-1001.pdf]