• 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