Information Technology Reference
In-Depth Information
The first one expresses a simple homogeneous linear form. The second one ex-
presses a symmetric linear form constituted by two parts having the same size, but
of two different types. The third one has an analogous structure with three parts.
This kind of form corresponds to an idealized form of development which is typi-
cal of many animal embryos (ectoderm, mesoderm, endoderm). In the next section,
we will present some grammars generating the languages corresponding to these
patterns.
6.2
Grammars and Chomsky Hierarchy
In Formal Language Theory a grammar is a formal device generating strings. In
this sense, a (formal) grammar is similar to a logical calculus equipped with axioms
from which it derives theorems. In fact, the first kinds of formal systems generating
strings, introduced by Post [208, 209], were inspired from the deduction systems of
formal logic. The following definition, due to Chomsky [196] is a particular case of
Post system.
Definition 6.1.
A (Chomsky) grammar
G
is a
generative
device. It is specified by
four components:
G
=(
A
,
T
,
S
,
R
)
•
A finite
alphabet
A
;
•
A subset
T
of
A
of
terminal
symbols;
•
an
initial symbol
S
belonging to
nonterminal
symbols in
A
−
T
;
A
∗
and
•
a finite set
R
of
rules
α
→
β
with
α
,
β
∈
α
=
λ
, that is, pairs of strings
over
A
.
A grammar
G
=(
A
,
T
,
S
,
R
)
defines a language by means of two relations: a
direct
⇒
G
:
rewriting
relation
⇒
G
,anda
transitive rewriting
relation
ϕ
⇒
G
ψ
iff
ϕ
=
γαδ
ψ
=
γβδ
α
→
β
∈
R
.
while
ϕ
⇒
G
ψ
iff for some sequence
ϕ
1
,
ϕ
2
,...,
ϕ
n
of strings:
ϕ
=
ϕ
1
⇒
G
ϕ
2
⇒
G
...⇒
G
ϕ
n
=
ψ
.
The language
generated by the grammar
G
is the set of strings of terminal
symbols obtained by
transitive rewriting
from the initial symbol
S
of
G
.
The language defined by the
bi-somatic pattern
is generated by the grammar of
Tab le 6 . 3 (
S
is the initial symbol, and terminal symbols are lower case letters).
L(
G
)
