Theory of Computation 
Section C

Pumping lemma for Regular Languages

Theorem

Let L be a regular language. Then there exists a constant ‘c’ such that for every string w in L:

|w| ≥ c

We can break w into three strings, w = xyz, such that:

1.  |y| > 0

2.  |xy| ≤ c

3.  For all k ≥ 0, the string xykz is also in L.

Applications of Pumping Lemma

Pumping Lemma is to be applied to show that certain languages are not regular. It should never be

used to show a language is regular.

1. If L is regular, it satisfies Pumping Lemma.

2. If L does not satisfy Pumping Lemma, it is non-regular.

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 w such that |w| ≥ 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.

Hence L is not regular.

ProblemProve that L = {aibi | i ≥ 0} is not regular.

Solution:

1. At first, we assume that L is regular and n is the number of states.

2. Let w = anbn. Thus |w| = 2n ≥ n.

3. By pumping lemma, let w = xyz, where |xy|≤ n.

4. Let x = ap, y = aq, and z = arbn, where p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0.  Thus

|y|≠ 0.

5. Let k = 2. Then xy2z = apa2qarbn.

6. Number of as = (p + 2q + r) = (p + q + r) + q = n + q

7. Hence, xy2z = an+q bn. Since q ≠ 0, xy2z is not of the form anbn.

8. Thus, xy2z is not in L. Hence L is not regular.