Theorem :
Let L be a regular language.
Then there exists a constant ‘c’ such that for every string s in L: |s| ≥ c
We can break w into three strings, s = xyz, such that:
1. |y| > 0
2. |xy| ≤ c
3. For all k ≥ 0, the string xykz is also in L.
Method to prove that a language L is not regular:
1. At first, we have to assume that L is regular.
2. So, the pumping lemma should hold for L.
3. Use the pumping lemma to obtain a contradiction:
(a) Select s such that |s| ≥ c
(b) Select y such that |y| ≥ 1
(c) Select x such that |xy| ≤ c
(d) Assign the remaining string to z.
(e) Select k such that the resulting string is not in L.
Proof: L = {anb2n}
Assume L is regular.
From the pumping lemma there exists a p such that every w ∈ L
such that |w| ≥ p can be represented as x y z with |y| ≠ 0 and |xy| ≤ p.
Let us choose apb2p.
Its length is 3p ≥ p.
Since the length of xy cannot exceed p, y must be of the form ak for some k > 0.
From the pumping lemma ap-kb2p must also be in Lbut it is not of the right form. Hence the language is not regular