![](http://image.absoluteastronomy.com/images//topicimages/noimage.gif)
Regulated rewriting
Encyclopedia
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:
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 ![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-5.gif)
3.-
is a finite set of matrices, which are non-empty sequences
,
with
, and
, where each
, is an ordered pair
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-11.gif)
being
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-12.gif)
these pairs are called "productions", and are denoted
. In these conditions the matrices can be written down as
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-14.gif)
4.- S is the start symbol
Definition
Let
be a matrix grammar and let ![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-16.gif)
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.
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-22.gif)
is generated by the![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-23.gif)
where
is the non-terminal set,
is the terminal set,
and the set of matrices is defined as
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-27.gif)
,
,
,
.
Definition
A Time Variant Grammar is a pair
where ![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-33.gif)
is a grammar and
is a function from the set of natural
numbers to the class of subsets of the set the productions.
where ![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-36.gif)
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.
A Grammar With Regular Control Language,
, is a pair
where ![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-40.gif)
is a grammar and
is a regular expression over the alphabet of the set the productions.
where
is the non-terminal set,
is the terminal set,
and the productions set is defined as
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-45.gif)
being
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-46.gif)
,
,
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-49.gif)
,
, 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
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-59.gif)
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
powerful grammatical device.
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
Basic concepts
DefinitionA Matrix Grammar,
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-1.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-2.gif)
1.-
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-3.gif)
2.-
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-4.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-5.gif)
3.-
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-6.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-7.gif)
with
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-8.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-9.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-10.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-11.gif)
being
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-12.gif)
these pairs are called "productions", and are denoted
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-13.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-14.gif)
4.- S is the start symbol
Definition
Let
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-15.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-16.gif)
the collection of all productions on matrices of
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-17.gif)
We said that
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-18.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-19.gif)
or "linear" or "without
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-20.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-21.gif)
The classic example (taken from [5] with change of nonterminals names)
The context-sensitive language![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-22.gif)
is generated by the
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-23.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-24.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-25.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-26.gif)
and the set of matrices is defined as
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-27.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-28.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-29.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-30.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-31.gif)
Time Variant Grammars
Basic conceptsDefinition
A Time Variant Grammar is a pair
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-32.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-33.gif)
is a grammar and
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-34.gif)
numbers to the class of subsets of the set the productions.
Definition
A Programmed Grammar is a pair![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-35.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-36.gif)
is a grammar and
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-37.gif)
to the class of subsets of the set the productions.
Basic concepts
DefinitionA Grammar With Regular Control Language,
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-38.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-39.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-40.gif)
is a grammar and
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-41.gif)
A naive example
Consider the CFG![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-42.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-43.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-44.gif)
and the productions set is defined as
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-45.gif)
being
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-46.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-47.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-48.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-49.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-50.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-51.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-52.gif)
Clearly,
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-53.gif)
Now, considering the productions set
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-54.gif)
define the regular expression over
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-55.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-56.gif)
Combining the CFG grammar
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-57.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-58.gif)
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-59.gif)
which generates the language
![](http://image.absoluteastronomy.com/images/formulas/6/8/3681188-60.gif)
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