Pumping Lemma for regular languages

• Suppose that a language L is regular. Then there is a FA that accepts L.
• Let n be the number of states of that FA. Then for any string x in L with |x| ≥ n, there are strings u, v and w which satisfy the following:
  • x = uvw
  • |uv| ≤ n
  • |v| > 0 is same as v ≠ ε
  • For every integer m ≥ 0, uv^mw ∈ L.
• If L is regular then for every x such that |x| ≥ n then there exists uvw such that x=uvw, v ≠ ε, |uv| ≤ n, and for which uvⁱw is in L for every i.

Pumping Lemma gives a necessity for regular languages.

Pumping Lemma is not a sufficiency, that is, even if there is an integer n that satisfies the conditions of Pumping Lemma, the language is not necessarily regular.

Pumping Lemma can not be used to prove the regularity of a language.

It can only show that a language is non-regular.

Example: L = a^kb^k is non-regular, where k is a natural number.

• Suppose that L is regular and let n be the number of states of an FA that accepts L. Consider a string x = aⁿbⁿ for that n.
• Then there must be strings u, v, and w such that
• x = uvw, |uv| ≤ n |v| > 0, and for every m ≥ 0, uv^mw ∈ L.
• Since |v| > 0, v has at least one symbol.
• Also since |uv| ≤ n, v = a^p, for some p > 0,
• Let us now consider the string uv^mw for m = 2.
• Then uv²w = a^n-pa^2pbⁿ = a^n+pbⁿ. Since p > 0 , n + p ≠ n .
• Hence a^n+pbⁿ can not be in the language L represented by a^kb^k.
• This violates the condition that for every m ≥ 0, uv^mw ∈ L.
• Hence L is not a regular language.

Pumping Lemma for CFL’s

• Let L be a CFL. Then there exists a constant N such that if z ∈L s.t. |z|≥N, then we can write z=uvwxy,
• |vwx| ≤ N
• vx ≠ ε
• For all k ≥ 0 : uv^kwx^ky ∈ L