Information Technology Reference
In-Depth Information
4.13 Properties of Context-Free Languages
In this section we derive properties of context-free languages. We begin by establishing a
pumping lemma that demonstrates that every CFL has a certain periodicity property. This
property, together with other properties concerning the closure of the class of CFLs under the
operations of concatenation, union and intersection, is used to show that the class is not closed
under complementation and intersection.
4.13.1 CFL Pumping Lemma
The pumping lemma for regular languages established in Section 4.5 showed that if a regular
language contains an infinite number of strings, then it must have strings of a particular form.
This lemma was used to show that some languages are not regular. We establish a similar result
for context-free languages.
LEMMA 4.13.1 Let G =( N , T , R , S ) be a context-free grammar in Chomsky normal form
with m non-terminals. Then, if w
2 m− 1 + 1 ,therearestrings r , s , t ,
L ( G ) and
|
w
|≥
2 m and for all integers n
u ,and v with w = rstuv such that
|
su
|≥
|
stu
|≤
1 and
0 ,
G rs n tu n v
L ( G ) .
S
a ,asubtreeofaparsetreeof
height h has a yield (number of leaves) of at most 2 h− 1 . To see this, observe that each rule
that generates a leaf is of the form A
Proof Since each production is of the form A
BC or A
a . Thus, the yield is the number of leaves in a binary
1, which is at most 2 h− 1 .
Let K = 2 m− 1 + 1. If there is a string w in L of length K or greater, its parse tree
has height greater than m . Thus, a longest path P in such a tree (see Fig. 4.31 (a)) has more
tree of height h
D
S
P
SP
A
D
z
b
x
a
A
y
s
u
t
(a)
(b)
Figure 4.31 L ( G ) is generated by a grammar G in Chomsky normal form with m non-
terminals. (a) Each w ∈ L ( G ) with | w |≥ 2 m− 1
+ 1 has a parse tree with a longest path P
containing at least m + 1 non-terminals. (b) SP ,theportionof P containing the last m + 1
non-terminals on P , has a non-terminal A that is repeated. The derivation A
s
u
can be
A
deleted or repeated to generate new strings in L ( G ) .
Search WWH ::




Custom Search