Theorem 2.1.1(Pumping Lemma): Let L ___* be a regular language. Then there exists an integer N (depending on L) with the property that for each z__L with len(z)N there exist u,v,w__* so that
i) z=uvw,
ii) len(uv)N and len(v)1, and
iii) uvkw__L for each k=0,1,2, ...
| Previous slide | Next slide | Back to first slide | View graphic version |