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.

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.

• 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.