Scribd
Upload
21 views3 pages

Pumping Lemma

The Pumping Lemma (PL) is a method used to demonstrate that certain languages are not regular by showing that they cannot satisfy specific conditions. The document provides a proof that the language A={anbn|n>=0} is not regular by analyzing different cases of string division and demonstrating that the conditions of the PL are violated. Additionally, it examines another language A={YY|Y€(0,1)*} and similarly shows that it cannot be regular using the same pumping length argument.

Uploaded by

aexe3006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views3 pages

Pumping Lemma

The Pumping Lemma (PL) is a method used to demonstrate that certain languages are not regular by showing that they cannot satisfy specific conditions. The document provides a proof that the language A={anbn|n>=0} is not regular by analyzing different cases of string division and demonstrating that the conditions of the PL are violated. Additionally, it examines another language A={YY|Y€(0,1)*} and similarly shows that it cannot be regular using the same pumping length argument.

Uploaded by

aexe3006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Pumping Lemma

1. PL is used to prove that a language is not regular


2. It cannot be used to prove that a language is regular

If A is a RL, then A has a pumping length ‘P’ such that any string ‘S’ where |S|>=P may be
divided into 3 parts S=XYZ such that the following conditions must be true
(1) xyiz € A for every i>=0
(2) |Y|>0
(3) |XY|<=P

Using PL prove that the language A={anbn|n>=0} is not regular

Assume A is regular

Pumping length = P

S= apbp

Divide S into X Y Z

P=7

S= aaaaaaabbbbbbb

Case 1 XYiZ->XY2Z / example i=2

Y is in ‘a’ part aa aaaaaaaa abbbbbbb

aa aaaa abbbbbbb

x y z 11≠7
case 2

Y is in ‘b’ part aaaaaaabb bbbbbbbb b

7≠11

aaaaaaabb bbbb b

x y z

case 3
aaaaa aabbaabb bbbbb

Y is in ‘a’ and ‘b’ part not follow pattern

aaaaa aabb bbbbb

x y z

|XY|<=P

P=7

CASE 1

6<=7

CASE 2

13<=7

CASE 3

9<=7

ALL THREE CASES CDTN NOT SATISFIED

2. A={YY|Y€(0,1)*}

Assume A is regular
It must have a pumping length = P
S=0p10p1
S->X Y Z
P=7
0000000100000001

00 0000 0100000001
X Y Z
XYiZ->XY2Z / example i=2

00 00000000 0100000001

String doesnot lie in the language

|y|>0

|XY|<=P

6<=7

You might also like