The Chomsky Hierarchy(review)
Languages
Recursively
Enumerable
Sets
Context-sensitive
Languages
Machines
Turing
Machines
Linear-bounded
Automata
Context-free
Languages
Pushdown
Automata
Regular
Languages
Finite State
Automata
Other Models
Post System
Markov Algorithms,
-recursive Functions
.
.
.
.
.
Regular
Expression
127
Proof of the Proper Containment of
the Language Hierarchy
Now we will prove the vertical relationship (i.e., the proper containment) of the
Chomsky hierarchy. We only prove the lower two levels. (Refer the text or other
related books for proofs of the remaining upper two levels.) It is trivial to prove that
every regular language is also a context-free language, and every language accepted
by a finite state machine can also be accepted by a pushdown automaton. Hence, for
the proof it is enough to show a context-free language that is not regular. To do this
we first show the following popular, so called, pumping lemma.
Pumping lemma. Let L be a regular language. Then there exists a constant n such
that, for every string z  L with |z|  n, there exist u,v,w   * such that
• z = uvw with |uv| n and
•|v|  1, such that
• for all i  0, uviw  L.
128
Proof of the lemma. If L is regular, then it is accepted by a DFA M = (Q,  ,  ,
q0 , F ). Let |Q| = n, and consider a string z   * of length m  n. Let z = a1a2 ...
am, and for every i, 1  i  m, let ( q0 , a1a2 ... ai ) = qi. Since n  m, i.e., the
number of states is less than or equal to the length of the string, there should be
two integers j and k, 0  j < k  n, such that qj = qk . (We can prove this using the
pigeonhole principle or proof by induction.) This implies that path qj ... qk is a
cycle of the state transition graph.
q0
a1
q1 a . . . . . a
2
j
qj
.....
aj+1
ak qk
.....
a m qm
Let u = a1 a2 ... aj, v = aj+1 aj+2 ... ak and w = ak+1 ak+2 ... am. Obviously, |uv|  n and
|v|  1. Clearly, if a1 a2 ... am = uvw  L (i.e, qm is in F), then we have
a1 a2 ... aj (aj+1 ... ak )i ak+1 ... am = uviw  L, for all i  0.
129
Application of the Pumping Lemma
We need to understand clearly what the lemma says before we use it. The lemma
can be rewritten as follows. It shows important logical segments to work with.
(1) For all regular languages L,
(2) there exists a constant n such that
(3) for all z  L with |z|  n,
(4) there exist u, v and w such that
(i) z = uvw,
(ii) |uv|  n,
(iii) |v|  1, and
(iv) for all i  0, uviw  L.
130
Application of the Pumping Lemma
Application Example . L = {aibi | i  0 } is not regular.
Proof (by contradiction). Suppose L is regular. Then it should satisfy parts (2) - (4) of
the pumping lemma. Let n be the constant (of part (2)) and pick z = anbn from L.
Clearly, z meets the length condition of part (3). Now, we examine if part (4) above is
true for z. If not, L does not satisfies the lemma, which implies that L cannot be a
regular language. Consider any u, v and w such that
(i) z = anbn = uvw
(ii) |uv|  n
(iii) |v|  1.
n
n
aa . . . . . . . . .abb . . . . . . . . .b
uv
w
Notice that by conditions (i), (ii) and (iii) above, v = aj, 1 j  n, i.e., string v contains
only a’s. We do not know exactly how many a’s are in v. It is enough to know that it has
only a’s. Now, consider string z' = uv2w = uvvw. Clearly, z' has more a’s than b’s, and
hence, z' cannot be a member of L. We are in a contradiction. L is not regular.
131
Ruminating on the Application of
the Pumping Lemma
Recall that, to disprove a statement which uses a universal quantifier (for example
“for all z”), it is enough to find one counter example. The lemma uses two universal
quantifiers in parts (3) and (4)-(iv). For these parts, it is enough to pick one counter
example, because our objective is to disprove the statement of the lemma. We picked z
= anbn for part (3), and i = 2 for part (4)-(iv). You may choose others if you like. But
for these parts, one counter example is enough.
To disprove a statement which uses an existential quantifier (for example “there is
n ..”, or “there exists u, v, w …”), we need to consider all such cases. Hence, in the
proof we use n like a variable. Whatever the value of the constant n is, we are using
that value of n. Notice that for u, v and w, we should consider all possible u, v and w
which satisfy conditions (i), (ii) and (iii).
132
Ruminating on the Application of
the Pumping Lemma (cont’ed)
The following example shows a typical case of “malicious” application of the pumping
lemma, which we frequently come across while grading tests for this course.
Question: Is the language L = {xyx | x = abc, y  {a,b,c}*} regular? Prove your answer.
Answer (wrong): L is not regular. Suppose that it is, and let n be the constant of the
pumping lemma. Consider z = abcyabc, where y  {a,b,c}* such that |y| > n. Obviously,
|z|  n. Let z = uvw, where u = a, v = b and w = cyabc. Then uv2w = abbcyabc is not in L!
Contradiction!
What is wrong with this proof?
construct an FA which accepts L.
Actually L is a regular language. We can easily
133
A non-regular language which satisfies
the pumping lemma
We learned that all regular languages satisfy the pumping lemma. We may ask the
following questions: Is there a non-regular language which satisfies the pumping
lemma? The answer is positive. Here is an example.
Let L1 = { x| x {a, b}*, and x has no substring of the form aa or bb}. L1, which is
regular, can also be expressed in terms of a regular expression, for example;
(ab)* + b(ab)* + (ab)*a +(ba)*.
Note that L1 has strings of all lengths. Let L2 = { x| x {a, b}* and |x| is a prime }, and
let L1 = {a,b}* - L1, the complement of L1. Consider the language;
L = (L1  L2)  L1 .
We will show that L is not regular and satisfies the pumping lemma. Suppose L is
regular, then L - L1 must be regular because L1 is regular. Use the pumping lemma with
a z  L - L by pumping z = uvw up to z' = uvp+1w, where p = |z|. Let j = |v|. Then we
1
have |z'| = | uvp+1w| = |uvw| + |vp| = p + jp = p(j+1), which is not prime. (Notice that p
is a prime number.) This implies that z is not in L - L1 . Hence, L - L1 is not regular.
We are in a contradiction. It follows that L cannot be regular.
134
Now, we show that L satisfies the pumping lemma. We choose n = 3 as the
constant of the lemma. For z  L such that |z|  3, let z = c1c2c3x, where c1, c2, c3 
{a, b}, and x   *. We will show that there exist u, v, w   * such that
(i) z = uvw, (ii) |uv|  n, (iii) |v|  1, (iv) uviw  L, for all i  0.
Consider the following three cases depending on c1, c2, and c3, :
Case 1: c1  c2  c3. Since c1, c2, c3  {a, b}, we have c1 = c3. Pump c2, i.e., let v = c2.
Clearly, for all i  0, z' = uviw is in L (actually, is in L1 except for the case i = 1).
(Notice that in this case z can be either in L1  L2 or L1 .)
Case 2: c1 = c2. Then z is in L1. Let v = c3. Then z' = uviw is in L (actually, in
all i  0.
Case 3: c2 = c3. Let v = c1. Then z' = uviw is in L, for all i  0 as in Case 2.
),L1for
135
The Pumping lemma for
context-free languages (uvwxy Theorem)
Theorem. For every CFL L whose size is not finite, there is a positive integer p such that,
for every z  L with |z|  p, there exist u, v, w, x, y   * such that
• z = uvwxy with |vwx| p and |vx|  1 such that
• for all i  0, uviwxiy  L.
This lemma can be rewritten as shown below to show the logical context. Notice that in
this lemma p has the same role as n has in the pumping lemma for regular languages,
and v and x, the “pumping sites”, can be anywhere in z. Recall that the “pumping site” v
in the regular language pumping lemma can only be located in the prefix of z of length n.
(1) For all context-free language L,
(2) there exists a constant p such that
(3) for all z  L such that |z|  p,
(4) there exist u, v, w, x, y, and z such that
(i) z = uvwxy,
(ii) |uwx|  p,
(iii) |ux|  1, and
(iv) for all i  0, uviwxiy  L.
136
Proof of the Pumping lemma for
context-free languages
Proof. (Sketch. See the text for detailed proof.) Consider the following CFG in the
Chomsky normal form.
S  AB
A  DE
B  FD
E  FG
G  DB | g
F  HG
Dd
Hh
The derivation tree for string z = d(hd)3hg(d)3dghdghd is given in the following
page. Notice the pattern of nonterminal sequence F-G-B-F-G-B-F-G-B which occurs
on the longest stem of the parse tree. It has a repeating pattern of F-G-B, which has
leaves “hd” to the left and “d” to the right. It is easy to see that we can “grow” the
stem by adding as many repeating patterns of F-G-B as we want or cut the it short by
deleting the pattern. The resulting tree is still a parse tree of the grammar. It follows
that the grammar has a parse tree for z' = d(hd)ihg(d)idghdghd, for all i  0, which
implies that z' is also in the language of the grammar.
137
S
A
D
B
E
d
F
H
h
D
h
D
d
h
B
d
H
G
h
g
H
G
h
g
d
d
B
H
G
D
B
F
H
D
D
D
G
F
d
F
d
F
H
B
D
G
d
F
G
G
D
d
S
AB
G
DB | g
A
DE
E
F
HG
H
h
FG
D
d
D
d
h
g
Z = d (h d)3 h g (d)3 d h g d h g d
u v w x
y
138
Proof of the Pumping lemma for
context-free languages(cont’ed)
In general, consider a parse tree of a CFG in CNF whose height is greater than the
number of nonterminal symbols of the grammar. Along the longest stem of the tree, at
least one nonterminal symbol, say A, appears more than once. Suppose that this parse
tree derives a sting z. Clearly, repeating (or deleting) the pattern from A to A along the
stem will result in another parse tree of the grammar which derives string z' = uviwxiy,
i  0, where uvwxy = z, |vx|  1 and |vwx|  |VN|, the number of nonterminal symbols.
139
Applications of the pumping lemma for CFL's
Example: The language L = { anbncn | n  0 }is not a CFL. Suppose L is a CFL, and
consider z = apbpcp, where p is the constant of the pumping lemma for CFL's. Clearly,
z is in L. Let z = uvwxy, where u,v,w,x and y are some substrings of z which satisfy
conditions (i) - (iii) above. Since |vwx|  p, substrings v and x together contain at
most two different symbols (see the illustration below). Since |vx|  1, v and x together
have at least one symbol. It follows that z' = uv2wx2y does not have the same number
of a's, b's and c's. Hence, z' is not in L. This contradicts the lemma. Thus language L is
not a CFL.
(i) z = apbpcp = uvwxy
(ii) |vwx|  p
(iii) |vx|  1.
p
p
p
aa . . . . . . . . .abb . . . . . . . . .bcc. . . . . . . . . c
vwx
y
u
140
Ruminating on the Application of
the Pumping Lemma for Contex-free Languages
Notice the difference between the pumping lemma for regular languages and
the lemma for CFL's. With the pumping lemma for regular languages, you have
privilege of pumping only on the prefix of length n of the string z that you have
chosen. With the pumping lemma for CFL's, you can no longer confine the
“pumpable site” within the prefix of z of length p. Notice that vwx, under the
condition that |uvx|  p, can be positioned anywhere because there is no restriction
on the length of the strings u and y. Hence, in general, we should deal with more
cases that result from pumping a string of a CFL than those when we pump a string
of a regular language. To deal with this difficulty, they developed more complex
pumping lemmas for CFL's (for example, see the Ogden's lemma in “Introduction
to Automata Theory, Languages, and Computation by Hopcroft, Motwani and
Ullman).
141
Descargar

Pumping Lemma for Regular Languages