• Let L be a RL. Then, there is k ³ 1 such that
if z Î L and |z| ³ k, then there exist u,v,w: z = uvw,
1) v ¹ e 2) |uv| £ k  3) for each m ³ 0, uvmw Î L
Pumping Lemma for RLs
Example: for RE r = ab*c, L(r) is regular.
• for z = abc: z Î L(r) & |z| ³ 3:
u v w
uv0w = ab0c = ac Î L(r)
uv1w = ab1c = abc Î L(r)
uv2w = ab2c = abbc Î L(r)
...
v ¹ e, |uv| = 2 £ 3
• for z = abbc: z Î L(r) & |z| ³ 3:
u v w
uv0w = abb0c = abc Î L(r)
uv1w = abb1c = abbc Î L(r)
uv2w = abb2c = abbbc Î L(r)
...
...
v ¹ e, |uv| = 2 £ 3
 Gist:
Pumping lemma demonstrates an infinite iteration of some substring in RLs.
There is k = 3 such that 1), 2) and 3) holds.
2/26