Pumping Lemma: Example
Prove that L = {anbn : n ³ 0} is not regular:
1) Assume that L is regular. Let k ³ 1 be
the pumping lemma constant for L.
2) Let z = akbk: akbk Î L, |z| = |akbk| = 2k ³ k
3) All
decompositions of z into uvw, v ¹ e, |uv| £ k:
8/26
u
v
w
a a…a abb…bb
k k
|uv| £ k
• pumping lemma: uv0w
Î L
k - i <
k
a abb…bb Ï L
u
w
• uv0w = uw =
Contradiction!
4) Therefore, L is not regular