Pumping Lemma
Lemma: (Pumping Lemma) If L is a regular language, then there exists a positive integer p (the pumping length) such that every string s ∈ L,|s | ≥p, can be partitioned into three pieces,s=xyz, such that the following conditions hold: 1.|y| > 0, 2.|xy| ≤p, and 3.for each i ≥0, xy i z Standard Example: 1.L={a n b n | n=0}is not regular. 2.L={1 n | n is a prime number}is not regular. 3.L={0 i 1 j | i > j}is not regular.