Pumping Lemma for Regular Grammars
A. Karthikeyan
Pumping Lemma for Regular grammars is said to be the toughest idea to understand. Here I tried it in my own way to make you to understand the concept. |
|||||||||
Pumping Lemma is a powerful tool to prove a language is not regular. The proof technique used here is Proof by Contradiction. ie., initially, in the proof, the language is considered as a regular language. The following table shows how and where pumping lemma used exactly:
The finite automata is simply a (virtual) machine and has no additional memory. It doesnot keep track of how many input symbols read. It just checks for whether the input string empties when reaching its final states. |
Below is the illustration done to understand the concept of Pumping Lemma:
In the above figure, the Conceptual Finite Automata is depicted by an ignorant person at the left side.He doesnot know whether the string("water") is in Language("bucket") or not. He simply pumps and pumps the string. Pumping lemma("Thatha") knows that some strings are not in language.(as he says,"water overflows")
One more illustration that considering pumping lemma as a GAME(taken from the well-known author - PETER LINZ):
In the above figure, the things in RED denotes the things tossed by opponent and in BLACK represents our representative's immediate move.
1) First the opponent declares as the language as regular and throws a 'k', that is the number of states.
2) With the available k, we are trying to select a string which has length greater than k.
3) Now opponent splits the string into three parts in such a way that w=xyz where
|xy| <=k and |y| >0
4) At last, we put various values to i(marked in BLACK). The moment once we get if xyz doesnot belong to the particular language, then the language is not regular. Thus WE WON.
Example
Show that L = { anbn | n>=1} is not regular.
1) Let us consider L is regular. Thus it has a finite automata to accept it. Let us consider k be the number of states. Also,if the finite automata exists,then it has atleast 1 state(ie.,k>=1).
2) Let us choose a string w=akbk
3) The w is splitted into three parts in such a way that |xy|<=k and |y| >0.
( y is not equal to epsilon)
| string | ==> mod operator denotes the length of the string.
xy (prefix part) contains entirely some 'a's.(because it has a length lesser than or equal to k).
So, let us have some assumptions like this -
x=at, t<k
y=ap, p<k and (t+p)<=k
z=ak-(t+p)bk
substituting these in w=xyiz=(at)(ap)i(ak-(t+p)bk)
4) putting i=0, we get w=ak-pbk actually this doesnot belongs to L. (there should be equal number of a's and b's). So, the L is not regular.
SO, WHO SAID PUMPING LEMMA IS AS DIFFICULT? |
Any doubts, please forward it my mail. [email protected]
Cartoons: A. Karthikeyan
| topics