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 xy^{k}z 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 = {a ^{n}b^{n+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 a^{p}b^{p+1 }. Its length is 2p + 1 ≥ p. Since the length of xy cannot exceed p, y must be of the form a^{k }for some k > 0. From the pumping lemma a^{p-k}b^{p+1 }must also be in L but it is not of the right form.

Hence the language is not regular.