Information Technology Reference
In-Depth Information
Ta b l e 6 . 6
A grammar for the bipartite language
S
aS
S
→
Sb
S
→
a
S
→
b
→
Ta b l e 6 . 7
Another grammar for the tri-somatic language
S
→
abc
S
→
S
a
abc
S
a
→
aS
b
S
b
a
→
aS
b
S
b
b
→
bbS
c
S
c
b
→
bS
c
S
c
c
→
S
cc
S
c
c
→
cc
bS
→
S
b
aS
→
aaS
b
The language defined by the
bipartite pattern
a
n
b
m
(
n
,
m
∈
N
,
n
+
m
=
0) is gener-
ated by the grammar of Table 6.6.
Another grammar generating the tri-somatic language is given in Table 6.7. The
idea behind its construction is that a special symbol “writes” a new terminal symbol
a
and transforms in a symbol moving on the right and searching for a symbol
b
.
When a
b
is reached it writes a new symbol
b
and transforms in a symbol search-
ing (on the right) for
c
.When
c
is reached a new symbol
c
is written and either
rewriting concludes, or a search (on the left) for
a
begins with another analogous
rewriting cycle. In this way, the synchronized rewriting of the three symbol, in the
right positions, is performed which guarantees the generation of tri-somatic forms.
The same strategy can be adapted for generating a lot of interesting linear patterns.
For example, the pattern of duplicated strings
can be generated with a similar
kind of strategy. In this kind of generative mechanism two possibilities are essen-
tial: i) moving a symbol along different parts of a string, which are possibly far and
at unbounded distances, and ii) transform a non-terminal symbol according to the
symbols occurring around it. These kinds of mechanisms can be realized only with
rules which rewrite more than one symbol.
The grammars given above correspond to different models of development of
linear structures. For example, in the bipartite pattern the only requirement is the
distinction of two parts an
a
-part on the left and a
b
-part on the right. In the case
of bi-somatic pattern, the two distinct parts are required to have the same size. This
means that
a
-part and
b
-part have to grow in a synchronized way. Finally, the tri-
somatic pattern extends, from two to three, the requirement of equal size and distinct
L(
α
)
