in Theory of Computation
558 views
2 votes
2 votes

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

 Answer Is Given 0000

 

in Theory of Computation
558 views

4 Comments

I found both option  b and c to be true but not a and d.
0
0
asking about strings of L* but not L.

option a also true along with b and d
0
0

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

2
2
sorry... I overlooked
0
0

1 Answer

5 votes
5 votes
Best answer

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.

selected by

Related questions