NPTEL Assignment

Question

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).

• A. 0000
• B. 010101
• C. 111101
• D. 010

 Answer Is Given 0000

 

Comments

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

---

asking about strings of L* but not L.

option a also true along with b and d

---

@Shaik Masthan 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

Answer 1

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.

so correct answer is B,C.