Definitions

# 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 = \left(N, T, M, S\right)$ where
1.- $N$ is an alphabet of non-terminal symbols
2.- $T$ is an alphabet of terminal symbols disjoint with $T$
3.- $M = \left\{m_1, m_2,..., m_n\right\}$ is a finite set of matrices, which are non-empty sequences $m_\left\{i\right\} = \left[p_\left\{i\right\},...,p_\left\{i_\left\{k\left(i\right)\right\}\right\}\right]$, with $k\left(i\right)geq 1$, and $1 leq i leq n$, where each $p_\left\{i_\left\{j\right\}\right\} 1leq jleq k\left(i\right)$, is an ordered pair $p_\left\{i_\left\{j\right\}\right\} = \left(L, R\right)$ being $L in \left(N cup T\right)^*N\left(Ncup T\right)^*, R in \left(Ncup T\right)^*$ these pairs are called "productions", and are denoted $Lrightarrow R$. In these conditions the matrices can be written down as $m_i = \left[L_\left\{i_\left\{1\right\}\right\}rightarrow R_\left\{i_\left\{1\right\}\right\},...,L_\left\{i_\left\{k\left(i\right)\right\}\right\}rightarrow R_\left\{i_\left\{k\left(i\right)\right\}\right\}\right]$
4.- S is the start symbol

Definition
Let $MG = \left(N, T, M, S\right)$ 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=\left(N, T, P, S\right)$ has the corresponding property.

### The classical example (taked from [5] with change of nonterminals names)

The context-sensitive language $L\left(G\right) = \left\{ a^nb^nc^n : ngeq 1\right\}$ is generated by the $CFMG$ $G =\left(N, T, M, S\right)$ where $N = \left\{S, A, B, C\right\}$ is the non-terminal set, $T = \left\{a, b, c\right\}$ is the terminal set, and the set of matrices is defined as $M :$ $left\left[Srightarrow abcright\right]$, $left\left[Srightarrow aAbBcCright\right]$, $left\left[Arightarrow aA,Brightarrow bB,Crightarrow cCright\right]$, $left\left[Arightarrow a,Brightarrow b,Crightarrow cright\right]$.

## Time Variant Grammars

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

## Programmed Grammars

Basic concepts

### Definition

A Programmed Grammar is a pair $\left(G, s\right)$ where $G = \left(N, T, P, S\right)$ is a grammar and $s, f: Prightarrow 2^\left\{P\right\}$ are the success and fail functions from the set of productions to 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 $\left(G, e\right)$ where $G = \left(N, T, P, S\right)$ is a grammar and $e$ is a regular expression over the alphabet of the set the productions.

### A naive example

Consider the CFG $G = \left(N, T, P, S\right)$ where $N = \left\{S, A, B, C\right\}$ is the non-terminal set, $T = \left\{a, b, c\right\}$ is the terminal set, and the productions set is defined as $P = \left\{p_0, p_1, p_2, p_3, p_4, p_5, p_6\right\}$ being $p_0 = Srightarrow ABC$ $p_1 = Arightarrow aA$, $p_2 = Brightarrow bB$, $p_3 = Crightarrow cC$ $p_4 = Arightarrow a$, $p_5 = Brightarrow b$, and $p_6 = Crightarrow c$. Clearly, $L\left(G\right) = \left\{ a^*b^*c^*\right\}$. Now, considering the productions set $P$ as an alphabet (since it is a finite set), define the regular expression over $P$: $e=p_0\left(p_1p_2p_3\right)^*\left(p_4p_5p_6\right)$.

Combining the CFG grammar $G$ and the regular expression $e$, we obtain the CFGWRCL $\left(G,e\right) =\left(G,p_0\left(p_1p_2p_3\right)^*\left(p_4p_5p_6\right)\right)$ which generates the language $L\left(G\right) = \left\{ a^nb^nc^n : ngeq 1\right\}$.

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 languages Academic Press, 1973 ACM monograph series

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

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

[4] Grammars with Regulated Rewriting Jurgen Dassow Otto-von-Guericke Available at: and ()

[5] Some questions of language theory S. Abraham in Proceedings of the 1965 International Conference On Computational Linguistics pp 1 - 11, Bonn, Germany Year of Publication: 1965 Available at:

Search another word or see Regulated rewritingon Dictionary | Thesaurus |Spanish