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 = {anbn+1}
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 apbp+1 . Its length is 2p + 1 ≥ 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-kbp+1 must also be in L but it is not of the right form.
Hence the language is not regular.