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 \(𝐴\) ?
- A.
011
- B.
0111
- C.
0011
- D.
001111
Attempted by 45 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.