Pumping Lemma

Pumping Lemma defines necessary properties for strings in a regular language. It can be used to show that languages are not regular. The pumping lemma only applies to languages (sets of strings) with infinite cardinality. It is recognizable if there exists a DFA for the language. If A and B both are recognizable, then AuB, AnB, AB.
Formally,
Let L be a regular language.  If L is recognizable, then there is a positive integer N such that for every string w€L with |w| ≥ n, x can be expressed as
w = uvx such that
1. |v| > 0
2. |uv| ≤ n
3. For all k ≥ 0, the string uv^kw is also in L.
Pumping Lemma for Regular sets
Let L be a regular set. Then there is a constant n such that if z is any word in L, and |z|>n, we may write z=uvw in such a way that |uv| ≤ n, |v| ≥ 1, and for all i ≥ 0, uvⁱw is in L. Further more, n is no greater than the number of states of the smallest DFSA accepting L.
The real strength of the Pumping Lemma is proving that languages are not regular.
– Proof by contradiction
• Assume that the language to be tested is regular
• Use the pumping lemma to come to a contradiction
• Original assumption about the language being
regular is false
You cannot prove a language to be regular using the Pumping Lemma!!!!