NPTEL

Question

Let L be a language. We define another language L′ as follow

L′={w∣w is binary equivalent of 2^x, where x∈L and consider x as a binary number}

Which of the following is false?

1) If L is regular then L′ is also regular

2) If L is regular then L′ may not regular

3) L′ is always regular irrespective of L

4) L′ is always non-regular irrespective of L

Comments

4 is false.

Answer 1

Let L={1^n 0^n | n>=1}  // This is not a regular language

That is L={10,1100,111000,11110000....................}

L' represents the binary  equivalent of the set { 2^2 ,2^12,  2^56 , 2^240 ,2^992...............}

L'= { 1.0^2 ,1.0^12 , 1.0^56 , 1.0^240 ,1.0^992...............}

L'  is  clearly not regular  since the number of 0's in the above sequence (2,12,56,240,992.......) cannot be recognized using FA.

From this it is possible to declare that statement 3 is false.

Let L be the set of all strings over 1* in which  number of 1's is even except epsilon //Regular language

 That is L={ 11 ,1111, 111111,............}

L' represents the binary equivalent of  the set { 2^3 , 2^15 , 2^63 , 2^255.................}

L'={ 1.0^3 , 1.0^15 ,1.0^63 ,1.0^255.............}

Here also L' is not  regular since the number of 0's in the  above  sequence (3,15,63,255......)  cannot be recognized using FA.

So statement 1 is clearly false

Statement 4 is false since every finite language is regular .

If L is finite then L' is also finite and regular.
 
So statement 2) is true

Here the word "may not" is the key. They are saying if L is regular then there are possibilities that L' may not be regular which is true.