Theory of Computation For each of the following languages gi

Theory of Computation: For each of the following languages, give the minimum pumping length and justify you answer. Please answer A through E, thank you for your help

a. 1001

b. 1 *01*

c. 11*00*1

d. (101)*0

e. 101 1 0

Solution

If L is regular language, then there is a number p(pumping ength)

such that w is any string in L of length p or more

can be written as w =xyz

(satisfying these conditions)

1.for each i>=0, xyⁱz belongs to L

2.lenght of y >0

2.length xy <=p

so we need to find the minimum length string w =xyz belongs to L, such tha xyⁱz should also belongs to L

A)1001

the minimum length string generated here is 1001 belongs to 1001

x=1,y=0,z=01   ,for all i>=0

so, the minimum pumping length is 4

B)1*01*

the minimum length string generated here is 10 belongs to 1*01*

x= epsilon, yⁱ =1, z=0,    for all i>=0

so, the minimum pumping length is 2

C)11*00*1

the minimum length string generated here is 1101 belongs to 11*00*1

x=1,yⁱ=1,z=01 for all i>=0

the minimum pumping lenth 4

D)(101)*0

the minimum length string generated here is 1010 belongs to (101)*1

x=epsilon,yⁱ=101,z=1 for all i>=0

the minimum pumping lenth 4

E)101U1*0

the minimum length string generated here is 10 belongs to 101U1*0

x= epsilon, yⁱ =1, z=0,    for all i>=0

so, the minimum pumping lengtH is 2