Pumping lemma
It is used to prove that a language is not regular. It cannot used to prove that a language is regular.
If A is a regular language then A has a pumping length P such that any string S where |s|>=P may be divided into three parts S=xyz such that the following conditions must be true :
i. xyiz where i≥0
ii. |y|>0
iii. |xy|≤P
To prove that a language is not regular using Pumping Lemma, follow the below steps:
1. Assume that A is regular language.
2. It has to have Pumping lemma say P.
3. All strings longer than P can be Pump i.e |s|≥P.
4. Divide S into xyz i.e in three parts.
5. Show that xyiz not belongs to A for some i.
6. Then consider all base that x can be divided into xyz.
7. Show that none of these conditions can satisfy Pumping lemma at the same time.
8. S cannot be Pump=Contradiction.
Example: using Pumping Lemma prove that a language A is not regular.
A={anbn n≥0 }
Solutions:
1. assume that A is regular language.
2. Assume that A is having Pumping lemma P.
3. Consider string S= apbp having pumping length P=7. [anbn=apbp i.e n=p]
4. Therefore string becomes S= aaaaaaabbbbbbb.
5. Divide S into three parts i.e xyz.
Case 1: The y part may be lie in a.
aa/x aaaaa/y bbbbbbb/z
case 2: The y part may be lie in b.
aaaaaaa/x bbbb/y bbb/z
case 3: The y part may be lie in a and b.
aaaa/x aaabb/y bbbb/z
now we have to prove all cases wrong according to the three conditions written above:
Prove case 1 wrong:
xyiz let i=2 =>xy2z =>x=aa , y=aaaaaaaaaa (after solving y2),z=bbbbbbb
aa/x aaaaaaaaaa/y bbbbbbb/z
no. of a’s=12 and no. of b’s=7 therefore a≠b , |y|>0
Prove case 2 wrong : xyiz let i=2 =>xy2z =>x=aaaaaaa , y=bbbbbbbb (after solving y2),z=bbb
aaaaaaa/x bbbbbbbb/y bbb/z
no. of a’s=7 and no. of b’s=11 therefore a≠b , |y|>0
prove case 3 wrong: xyiz let i=2 =>xy2z =>x=aaaa , y=aaaaaabbbb (after solving y2),z=bbbbb
aaaa/x aaaaaabbbb/y bbbbb/z
no. of a’s=10 and no. of b’s=9 therefore a≠b , |y|>0
Therefore the language A is not a regular language.