Pumping Lemma For Regular Grammars

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 −

|y| > 0

|xy| ≤ c

For all k ≥ 0, the string xy^kz is also in L.

Apppcations of Pumping Lemma

Pumping Lemma is to be appped to show that certain languages are not regular. It should never be used to show a language is regular.

If L is regular, it satisfies Pumping Lemma.

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

Method to prove that a language L is not regular

At first, we have to assume that L is regular.

So, the pumping lemma should hold for L.

Use the pumping lemma to obtain a contradiction −

Select w such that |w| ≥ c

Select y such that |y| ≥ 1

Select x such that |xy| ≤ c

Assign the remaining string to z.

Select k such that the resulting string is not in L.

Hence L is not regular.

Problem

Prove that L = {aⁱbⁱ | i ≥ 0} is not regular.

Solution −

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

Let w = aⁿbⁿ. Thus |w| = 2n ≥ n.

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

Let x = a^p, y = a^q, and z = a^rbⁿ, where p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Thus |y| ≠ 0.

Let k = 2. Then xy²z = a^pa^2qa^rbⁿ.

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

Hence, xy²z = a^n+q bⁿ. Since q ≠ 0, xy²z is not of the form aⁿbⁿ.

Thus, xy²z is not in L. Hence L is not regular.