Information Technology Reference
In-Depth Information
REC
⊂
RE
.
The inclusion of the class
CS
=
L
1
in the class
RE
is a consequence of the monotony
condition for the grammars of type 1. Moreover, the existence of a language of
REC
which does not belong to
CS
can be obtained by a kind of reasoning going back to
Cantor and Russell (
the diagonal argument
).
It can be shown that any rule of type 1 is equivalent, from the generative point
of view, to a set of rules having the following
context-sensitive
form, where
X
is a
non-terminal symbol and
α
,
β
,
γ
are strings of the alphabet
A
with
γ
=
λ
:
α
X
β
→
αγβ
.
Languages generated by grammars with context-sensitive rules are also called
context-sensitive
and their class is denoted by
CS
. Therefore,
CS
=
L
1
. Rules of
type 2 are called
context-free
and languages generated by grammars of type 2 are
also denoted by
CF
. Therefore,
CF
=
L
2
.
In the next section we show that
L
3
coincides with the class
REG
of
regular
languages
obtainable from finite languages by applying the language operations of
concatenation, sum, and Kleene star.
If
X
,
Y
are non-terminal symbols and
a
is terminal symbol, then
X
→
aY
is a
right-linear rule
, while
X
→
Ya
is a
left-linear rule
,and
X
→
a
is at same time
right-linear and left-linear.
Grammars with both types of rules right-linear and left-linear generate the class
LIN
of linear languages which is strictly included in
CF
and which strictly includes
REG
.
In conclusion, Chomsky hierarchy can be reformulated and extended in the fol-
lowing way:
FIN
⊂
REG
⊂
LIN
⊂
CF
⊂
CS
⊂
REC
⊂
RE
.
Two important aspects of grammatical generation which are interrelated are cru-
cial: i) rules are applied without no strategy, ii) terminal symbols are the only mech-
anism for discriminating, among the strings generated from
S
, those which belong
to the language
L(
)
. It can be shown that if we do not use terminal symbols,
then the generation power of grammars is reduced. In this way, the terminal/non-
terminal distinction plays the role of integrating the rules toward the realization of
forms which are specific of a given language. In other words, only string genera-
tions where rules are applied in a “correct” way are able to “terminalize”. The other
generations can be viewed as unsuccessful trials in a specific process of string gen-
eration.
Natural languages, programming languages, and strings representing linear forms
that occur in natural processes require grammars having a complexity between
context-free and context-sensitive grammars.
G
