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