Regular language

Lemma

(pumping lemma): for every regular language L, there exists >0 (a.k.a. pumping length) s.t. every sL with |s| can be written as s=xyz with with i0xyizL,|y|>0,|xy|0