Proof of Pumping Lemma 3/3
•
T
here exist moves:
•
f
or
m
= 0
,
u
v
m
w
=
u
v
0
w
=
u
w
,
1.
2.
3.
s
u
w
|
–
i
q
w
|
–
*
f
,
f
Î
F
1.
3.
•
f
or each
m
>
0
,
s
u
v
m
w
|
–
i
q
v
m
w
|
–
*
f
,
f
Î
F
1.
3.
|
–
j
q
v
m
-
1
w
2.
|
–
j
q
w
|
–
j
...
2.
2.
Summary:
1)
q
v
|
–
j
q
,
j
³
1
; therefore,
|
v
|
³
1
, so
v
¹
e
2)
s
u
v
|
–
i
q
v
|
–
j
q
,
i + j
£
k
; therefore,
|
u
v
|
£
k
3)
For each
m
³
0:
s
u
v
m
w
|
–
*
f
,
f
Î
F
, therefore
u
v
m
w
Î
L
QED
s
u
|
–
i
q
;
q
v
|
–
j
q
;
q
w
|
–
*
f
,
f
Î
F
,
so
6
/26