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:

Basic concepts

Definition

A Matrix Grammar, , is a four-tuple where

1.- is an alphabet of non-terminal symbols

2.- is an alphabet of terminal symbols disjoint with

3.- is a finite set of matrices, which are non-empty sequences
,
with , and
, where each
, is an ordered pair

being

these pairs are called "productions", and are denoted
. In these conditions the matrices can be written down as


4.- S is the start symbol


Definition

Let be a matrix grammar and let
the collection of all productions on matrices of .
We said that is of type i according to Chomsky's hierarchy with , or "increasing length"
or "linear" or "without -productions" if and only if the grammar has the corresponding property.

The classic example (taken from [5] with change of nonterminals names)

The context-sensitive language

is generated by the
where
is the non-terminal set,
is the terminal set,
and the set of matrices is defined as

,
,
,
.

Time Variant Grammars

Basic concepts

Definition

A Time Variant Grammar is a pair where
is a grammar and is a function from the set of natural
numbers to the class of subsets of the set the productions.

Definition

A Programmed Grammar is a pair where
is a grammar and are the success and fail functions from the set of productions
to the class of subsets of the set the productions.

Basic concepts

Definition

A Grammar With Regular Control Language,
, is a pair where
is a grammar and is a regular expression over the alphabet of the set the productions.

A naive example

Consider the CFG
where
is the non-terminal set,
is the terminal set,
and the productions set is defined as

being

,
,

,
, and
.
Clearly,
.
Now, considering the productions set
as an alphabet (since it is a finite set),
define the regular expression over :
.

Combining the CFG grammar and the regular expression
, we obtain the CFGWRCL

which generates the language
.
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

Turing machine

A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

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:
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. Abraham
in Proceedings of the 1965 International Conference On Computational Linguistics
pp 1 - 11, Bonn, Germany Year of Publication: 1965
Available at:
http://acl.ldc.upenn.edu/C/C65/C65-1001.pdf