Information Technology Reference
In-Depth Information
Ta b l e 6 . 2
The language
L(
G
)
generated by the grammar
G
L(
G
)=
{
α
∈
T
∗
|
S
⇒
G
α
}
Ta b l e 6 . 3
A grammar for the bi-somatic language
S
→
ab
S
→
aSb
In fact, by applying the second rule a certain number
n
of times,
n
symbols
a
are
generated as prefix of
S
followed by
n
symbols
b
as suffix. With the first rule
S
is
replaced by
ab
, therefore instances of the bi-somatic pattern are always produced.
The language defined by the
tri-somatic
pattern is generated by the grammar of
Tab le 6 . 4.
Ta b l e 6 . 4
A grammar for the tri-somatic language
S
→
abc
S
→
aSBc
cB
→
Bc
bB
→
bb
In fact, by applying the first two rules we get a string with a number
n
of symbols
a
asaprefix,followedbyastring
abc
and by the same number
n
of pairs
Bc
.The
last two rules of the grammar move symbols B in the middle and symbols
c
at the
end of the string. When a symbol
B
comes on the right of a symbol
b
it transforms
into
b
, according to the last rule. In this way all the
B
which reach the middle of the
string become
b
, but the number of
B
is equal to the number of
a
and of
c
. Therefore,
instances of the tri-somatic pattern are always produced by the grammar of Table
6.4. Moreover, it is easy to verify that, for whatever is the order of application of the
last two rules, the same terminal string is generated.
The mono-somatic language defined by the pattern
a
n
(
n
>
0) is generated by the
grammarofTable6.5.
Ta b l e 6 . 5
A grammar for the mono-somatic language
S
→
aS
S
→
a
