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:
Definition
A Matrix Grammar,
M
G
, 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
=
m
1
,
m
2
,
.
.
.
,
m
n
is a finite set of matrices, which are non-empty sequences
m
i
=
[
p
i
1
,
.
.
.
,
p
i
k
(
i
)
]
, with
k
(
i
)
≥
1
, and
1
≤
i
≤
n
, where each
p
i
j
1
≤
j
≤
k
(
i
)
, is an ordered pair
p
i
j
=
(
L
,
R
)
being
L
∈
(
N
∪
T
)
∗
N
(
N
∪
T
)
∗
,
R
∈
(
N
∪
T
)
∗
these pairs are called "productions", and are denoted
L
→
R
. In these conditions the matrices can be written down as
m
i
=
[
L
i
1
→
R
i
1
,
.
.
.
,
L
i
k
(
i
)
→
R
i
k
(
i
)
]
4.- S is the start symbol
Definition
Let
M
G
=
(
N
,
T
,
M
,
S
)
be a matrix grammar and let
P
the collection of all productions on matrices of
M
G
. We said that
M
G
is of type i according to Chomsky's hierarchy with
i
=
0
,
1
,
2
,
3
, or "increasing length" or "linear" or "without
λ
-productions" if and only if the grammar
G
=
(
N
,
T
,
P
,
S
)
has the corresponding property.
Note: taken from Abraham 1965, with change of nonterminals names
The context-sensitive language
L
(
G
)
=
{
a
n
b
n
c
n
:
n
≥
1
}
is generated by the
C
F
M
G
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
:
[
S
→
a
b
c
]
,
[
S
→
a
A
b
B
c
C
]
,
[
A
→
a
A
,
B
→
b
B
,
C
→
c
C
]
,
[
A
→
a
,
B
→
b
,
C
→
c
]
.
Basic concepts
Definition
A Time Variant Grammar is a pair
(
G
,
v
)
where
G
=
(
N
,
T
,
P
,
S
)
is a grammar and
v
:
N
→
2
P
is a function from the set of natural numbers to the class of subsets of the set of productions.
Basic concepts
A Programmed Grammar is a pair
(
G
,
s
)
where
G
=
(
N
,
T
,
P
,
S
)
is a grammar and
s
,
f
:
P
→
2
P
are the success and fail functions from the set of productions to the class of subsets of the set of productions.
Definition
A Grammar With Regular Control Language,
G
W
R
C
L
, 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.
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
=
S
→
A
B
C
p
1
=
A
→
a
A
,
p
2
=
B
→
b
B
,
p
3
=
C
→
c
C
p
4
=
A
→
a
,
p
5
=
B
→
b
, and
p
6
=
C
→
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
1
p
2
p
3
)
∗
(
p
4
p
5
p
6
)
.
Combining the CFG grammar
G
and the regular expression
e
, we obtain the CFGWRCL
(
G
,
e
)
=
(
G
,
p
0
(
p
1
p
2
p
3
)
∗
(
p
4
p
5
p
6
)
)
which generates the language
L
(
G
)
=
{
a
n
b
n
c
n
:
n
≥
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.
