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 =$ is a finite set of matrices, which are non-empty sequences
m_ = _,...,p_/math>,
with $k(i)\geq 1$, and
$1 \leq i \leq n$, where each
$p_ 1\leq j\leq k(i)$, is an ordered pair
$p_ = (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 = _\rightarrow R_,...,L_\rightarrow R_/math>

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) = \$
is generated by the $CFMG$
$G =(N, T, M, S)$ where
$N = \$ is the non-terminal set,
$T = \$ is the terminal set,
and the set of matrices is defined as
$M :$
\left \rightarrow abc\right/math>,
\left \rightarrow aAbBcC\right/math>,
\left \rightarrow aA,B\rightarrow bB,C\rightarrow cC\right/math>,
\left \rightarrow a,B\rightarrow b,C\rightarrow c\right/math>.

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\rightarrow 2^$ 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^$ 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 = \$ is the non-terminal set,
$T = \$ is the terminal set,
and the productions set is defined as
$P = \$
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) = \$.
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) = \$.

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 (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,

Formal languages
Formal methods