Computer Science 456/656: the Pumping Lemmas

Pumping Lemma for Regular Languages. For any regular language L There exists a number p (called the pumping length of L such that For any string w ∈ L of length at least p There exist strings x, y, and z such that

1. xyz = w

2. |xy| ≤ p

3. y is not the empty string

4. For any integer i ≥ 0 xy^{i}z ∈ L

Pumping Lemma for Context-Free Languages. For any context-free language L There exists a number p (called the pumping length of L such that For any string w ∈ L of length at least p There exist strings u, v, x, y, and z such that

1. uvxyz = w

2. |vxy| ≤ p

3. v and y are not both the empty string

4. For any integer i ≥ 0 uv^{i}xy^{i}z ∈ L