558 views

Let L={w| w has even length and odd number of 0’s}. Which of the following words is in L* (Kleen Closure of L).

1. 0000
2. 010101
3. 111101
4. 010

I found both option  b and c to be true but not a and d.

option a also true along with b and d

sir can how you show option a is true ?

for 0000 which has length 4 we have to concat with

1. length 0 + length 4
2. length 1+  length 3
3. length 2+ length  2

now here in the language smallest string is length 2 which is “01” or “10”.

so How L* can have it ?

As L* is union of L^0 ,L^1,L^2..

sorry... I overlooked

The correct answer is option B.

L ={ 01,10,….}

L^2=L.L={01,10,….}.{01,10,…..}

L^2={0101,0110,1001,1010,…….}

L^3=L^2.L={0101,0110,1001,1010…..}.{01,10,….}

L^3   ={010101,010110,100101,…..}

L*=L^0 U L^1 U L^2 U L^3….

so definitely the string 010101 will be there.

Now 0000 can never be generated as

for 0000 which has length 4 we have to concat with

1. length 0 + length 4
2. length 1+  length 3
3. length 2+ length  2

now here in the language smallest string is length 2 which is “01” or “10” so by concatenate them we cant get “0000”  and L itself does not contain “0000”.

option c the string “111101” is present in the language ,it has even length and odd no of zero . So it will be in L*.

Option D is also not in the L* as it can be generate by concate either

1. zero length string + 3 length string
2. 1 length string + 2 length

Now L does not not contain “010”

we cant have this as well.