Pumping Lemma for Regular Languages
The language accepted by the finite automata is called Regular Language. If we are given a language L and asked whether it is regular or not? So, to prove a given Language L is not regular we use a method called Pumping Lemma.
The term Pumping Lemma is made up of two words:
- Pumping: The word pumping refers to generate many input strings by pushing a symbol in an input string again and again.
- Lemma: The word Lemma refers to intermediate theorem in a proof.
Pumping Lemma is used to prove that given language is not regular. So, first of all we need to know when a language is called regular. A language is called regular if:
- Language is accepted by finite automata.
- A regular grammar can be constructed to exactly generate the strings in a language.
- A regular expression can be constructed to exactly generate the strings in a language.
Principle of Pumping Lemma
The pumping lemma states that all the regular languages have some special properties. If we can prove that the given language does not have those properties, then we can say that it is not a regular language.
Theorem 1: Pumping Lemma for Regular Languages
If L is an infinite regular language then there exists some positive integer n (pumping length) such that any string w ∈ L has length greater than or equal to n. i.e. |w| >=n, then string can be divided into three parts, w=xyz satisfying the following condition:
- For each i>=0, xyiz ∈ L.
- |y| > 0
- |xy| <= n
|w| represents the length of string w and yimeans that i copies of y are concatenated together, y0 = ∈.
Applying Pumping Lemma
We will use above theorem to prove that given language is not regular. The steps needed to prove that given languages is not regular are given below:
Step1: Assume L is a regular language in order to obtain a contradiction. Let n be the number of states of corresponding finite automata.
Step2: Now chose a string w in L that has length n or greater
i.e. |w| >= n. use pumping lemma to write
w = xyz with |xy| <= n and |y| = 0.
Step3: Finally demonstrate that we cannot pumped by considering all ways of dividing w into x, y and z, and for each such division find a value of I such that xyiz ∉ L. This contradicts our assumption; hence L is not regular.
We prove xyiz ∉ L by considering the length of xyz i.e. |xyiz| or by using the structure of strings in L.
Example
Let L= { anbn | n>=0 }. By using pumping lemma show that L is not regular language.
Solution:
Step1: Assume L is a regular language in order to obtain contradiction. Let n be the number of states in finite automata accepting L.
Step2: Let w = anbn, then |w| = 2n > n. Using pumping lemma, we can demonstrate w in three parts of xyz such that w = xyz with |xy| <=n and |y| > 0.
Step3: Now we want to find i, xyiz ∈ L.
There are three possibilities for y, we will consider all cases one by one and show that given language contains some string not for { anbn | n>=0 }.
Case 1: The string y consists of only a’s i.e. y = ak (k>=1).
We have w = xyz
w = anbn
In given language we have equal numbers of a’s and b’s w ∈ L so it must satisfy this condition. Let us take i=0.
As xyz = anbn
xz = an-kbn
n-k ≠ n
So xz ∉ L. This case is a contradiction.
Case 2: The string y consists of only b’s i.e. y = bm (m >= 1).
We have w = xyz
w = anbn
In given language, we have equal number of a’s and b’s w ∈ L, so it must satisfy this condition. Let us take i=0.
As xz = anbn-m
xz = an-kbn
Where n ≠ m
So xz ∉ L. This case also gives contradiction.
Case 3: The string y consists of both a’s and b’s i.e. y = akbm (k,m >= 1).
We have w = xyz
w = anbn
w = an-kakbm bn-m
In given language we have equal number of a’s and b’s w ∈ L, so it must satisfy this condition. Let us take i=2.
xy2z = xyyzi
= an-kakbmkbm bn-m
In this case, the string xyyz must have equal number of a’s and b’s but they are out of order with some b’s before a’s. Hence it is not a member of L. which contradicts our assumption.
Thus, in all cases we get a contradiction. Therefore, L is not regular.
