Consider Language \(š“\) defined over the alphabet \(Ī£=\{0,1\}\) asā¦
2015
Consider LanguageĀ \(š“\)Ā defined over the alphabetĀ \(Ī£=\{0,1\}\)Ā as
\(A=\{0^{\lfloor n/2 \rfloor} 1^n :n>=0 \}\)
The expressionĀ \(āš/2ā\)Ā means the floor ofĀ \(š/2\), or what you get by roundingĀ \(š/2\)Ā down to the nearest integer.
Which of the following is not an example of a string inĀ \(š“\)Ā ?
Answer: C. 0011 ā Approach: For a string to be in A it must have n ones and exactly floor(n/2) leading zeros. Let k be the number of 0s and m be the number of 1s; then we mustā¦
- A.
011
- B.
0111
- C.
0011
- D.
001111
Attempted by 69 students.
Show answer & explanation
Correct answer: C
Approach: For a string to be in A it must have n ones and exactly floor(n/2) leading zeros. Let k be the number of 0s and m be the number of 1s; then we must have m = n and k = floor(m/2). Check each candidate string by counting zeros and ones.
For the string 011: zeros = 1, ones = 2. Here n = 2 and floor(n/2) = 1, so the number of zeros matches. Therefore 011 is in A.
For the string 0111: zeros = 1, ones = 3. Here n = 3 and floor(n/2) = 1, so the number of zeros matches. Therefore 0111 is in A.
For the string 0011: zeros = 2, ones = 2. Here n = 2 and floor(n/2) = 1, but there are 2 zeros, so the string does not match the required form. Therefore 0011 is not in A.
For the string 001111: zeros = 2, ones = 4. Here n = 4 and floor(n/2) = 2, so the number of zeros matches. Therefore 001111 is in A.
Conclusion: The only string among the choices that is not in A is 0011.