Information Technology Reference
In-Depth Information
than
m
non-terminals on it. Consider the subpath
SP
of
P
containing the last
m
+
1
non-terminals of
P
.Let
D
be the first non-terminal on
SP
and let the yield of its parse tree
be
y
. It follows that
2
m
.Thus,theyieldofthefullparsetree,
w
,canbewrittenas
w
=
xyz
for strings
x
,
y
,and
z
in
|
y
|≤
T
∗
.
By the pigeonhole principle stated in Section
4.5
, some non-terminal is repeated on
SP
.
Let
A
be such a non-terminal. Consider the first and second time that
A
appears on
SP
.
(See Fig.
4.31
(b).) Repeat all the rules of the grammar
G
that produced the string
y
except
for the rule corresponding to the first instance of
A
on
SP
and all those rules that depend
on it. It follows that
D
∗
T
∗
. Similarly, apply all the rules to
the derivation beginning with the first instance of
A
on
P
up to but not including the rules
beginning with the second instance of
A
. It follows that
A
⇒
⇒
a
A
b
where
a
and
b
are in
T
∗
s
A
u
,where
s
and
u
are in
and at least one is not
since no rules of the form
A
→
B
are in
G
. Finally, apply the rules
starting with the second instance of
A
on
P
.Let
A
∗
⇒
t
be the yield of this set of rules. Since
A
∗
s
A
u
and
A
⇒
t
, it follows that
L
also contains
xatbz
.
L
also contains
xas
n
tu
n
bz
⇒
1because
A
⇒
s
A
u
can be applied
n
times after
A
⇒
s
A
u
and before
A
⇒
for
n
≥
t
.Now
let
r
=
xa
and
v
=
bz
.
We use this lemma to show the existence of a language that is not context-free.
LEMMA
4.13.2
The language
L
=
{a
n
b
n
c
n
|
n
≥
0
}
over the alphabet
Σ=
{
a
,
b
,
c
}
is not
context-free.
Proof
We assume that
L
is context-free generated by a grammar with
m
non-terminals and
show this implies
L
contains strings not in the language. Let
n
0
=
2
m−
1
+
1.
Since
L
is infinite, the pumping lemma can be applied. Let
rstuv
=
a
n
b
n
c
n
for
n
=
n
0
. From the pumping lemma
rs
2
tu
2
v
is also in
L
. Clearly if
s
or
u
is not empty (and at
least one is), then they contain either one, two, or three of the symbols in
Σ
.Ifoneofthem,
say
s
, contains two symbols, then
s
2
contains a
b
before an
a
or a
c
before a
b
,contradicting
the definition of the language. The same is true if one of them contains three symbols.
Thus, they contain exactly one symbol. But this implies that the number of
a
's ,
b
's , and
c
's
in
rs
2
tu
2
v
is not the same, whether or not
s
and
u
contain the same or different symbols.
4.13.2 CFL Closure Properties
In Section
4.6
we examined the closure properties of regular languages. We demonstrated that
they are closed under concatenation, union, Kleene closure, complementation, and intersec-
tion. In this section we show that the context-free languages are closed under concatenation,
union, and Kleene closure but not complementation or intersection. A class of languages is
closed under an operation if the result of performing the operation on one or more languages
in the class produces another language in the class.
The concatenation, union, and Kleene closure of languages are defined in Section
4.3
.The
concatenation of languages
L
1
and
L
2
, denoted
L
1
·
L
2
, is the language
{
uv
|
u
∈
L
1
and
v
∈
L
2
}
L
2
, is the set of strings that are in
L
1
or
L
2
or both. The Kleene closure of a language
L
, denoted
L
∗
and called the Kleene star, is
. The union of languages
L
1
and
L
2
, denoted
L
1
∪
the language
i
=
0
L
i
where
L
0
=
and
L
i
=
L
L
i−
1
.
{
}
·
THEOREM
4.13.1
The context-free languages are closed under concatenation, union, and Kleene
closure.
Search WWH ::
Custom Search