Added to Favorites

Related Searches

Nearby Words

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 $Lrightarrow\; 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

### 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[Srightarrow\; abcright]$,
$left[Srightarrow\; aAbBcCright]$,
$left[Arightarrow\; aA,Brightarrow\; bB,Crightarrow\; cCright]$,
$left[Arightarrow\; a,Brightarrow\; b,Crightarrow\; cright]$.
## 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 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:\; Prightarrow\; 2^\{P\}$ 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 $(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\; =\; 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(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)$.## Sources

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 $Lrightarrow\; 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.

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 the productions.

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.

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.

[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:

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Monday September 15, 2008 at 09:02:40 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Monday September 15, 2008 at 09:02:40 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.