Proof of Pumping Lemma 1/3
•
Let
L
be a regular language. Then, there exists
DFA
M
= (
Q
,
S
,
R
,
s
,
F
), and
L
=
L
(
M
).
•
For
z
Î
L
(
M
)
,
M
makes
|
z
| moves and
M
visits
|
z
|
+
1
states:
s
a
1
a
2
…
a
n
|
–
q
1
a
2
…
a
n
|
–
…
|
–
q
n
-1
a
n
|
–
q
n
|
z
|
|
z
|
+
1
states
q
1
s
q
n
a
1
a
2
…
q
n
-1
a
n
•
for
z
=
a
1
a
2
...
a
n
:
a
n
-1
4
/26