UGC NET CSE | December 2015 | Part 3 | Question: 73

Question

Consider Language $A$ defined over the alphabet $\Sigma=\{0,1\}$ as $A=\{0^{\lfloor n/2 \rfloor} 1^n :n>=0 \}$ 

The expression $\lfloor n/2 \rfloor$ means the floor of $n/2$, or what you get by rounding $n/2$ down to the nearest integer.

Which of the following is not an example of a string in $A$?

• A. $011$
• B. $0111$
• C. $0011$
• D. $001111$

Comments

yes

Answer 1

ANSWER IS (C)

if n=2
[n/2] = [1] = 1 i.e. Language is : 011

if n=3
[n/2] = [1.5] = 1 i.e. Language is : 0111

if n=4
[n/2] = [2] = 2 i.e. Language is : 001111

Hence option A is possible, B is possible, D is possible but C is not possible.

Comments

Hi can you please make me understand what is the exact meaning of 2nd line and what type of language it is .

---

the language is cfl...

wat is d problem in 2nd line itz easy

Answer 2

ans is 3

put n=1 A will become 1   (as floor (n/2) =floor(1/2) =0)

put n=2 A will become 011 which is choice 1  as floor(2/2)=floor(1)=1

put n=3 A will become 0111  which is choice no 2

put n=4 A will become 001111 which is choice no 4

only choice 3 is not possible

Answer 3

3.should be the ans.

N(0) must be floor( N(1) /2 )

Where N(0) means num.of 0's

Answer 4

GIVEN:

A={0^[n/2] 1^n : n>=0} the expression [n/2] means that floor of n/2 or by rounding [n/2],which of the following string is not the example of A

SOLUTION:

option(1) =011

A={0^[n/2] 1^n : n>=0} [i.e.,1^n= so the value of n can be identified by the number of '1' in the option]

so the value of n=2 ==>0^[2/2] 1^2=>(0^1) (1^2)=011 is satisfying condition.

option(2)=0111

so the value of n=3 ==>0^[3/2] 1^3=>(0^1) (1^3)=0111 is satisfying condition.

option(3)=0011

so the value of n=2 ==>0^[2/2] 1^2=>(0^1) (1^2)=011 is not  satisfying condition.

option(4)=001111

so the value of n=4 ==>0^[4/2] 1^4=>(0^2) (1^4)=0111 is satisfying condition.

so the Answer is option (3) is correct.