GATE 2024 CS2 Q.62: solution and answer

Official answer: 15Source: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

1. Read the expression $b^{\ast }a{b}^{\ast }(a{b}^{\ast }a{b}^{\ast }{)}^{\ast }$. The first part $b^{\ast }a{b}^{\ast }$ contains exactly one $a$. Each repetition of $(a{b}^{\ast }a{b}^{\ast })$ adds exactly two more $a$'s. The $b$'s can sit anywhere between the $a$'s.

2. So every string in $L_1$ has an odd number of $a$'s, which means at least one. Conversely, take any string with an odd number of $a$'s. Its first $a$ is matched by the leading $a{b}^{\ast }$ part, and the remaining $a$'s pair up in order. The $b$'s between them are absorbed by the $b^{\ast }$ parts. Hence $L_1=\{w\in \{a,b{\}}^{\ast }\mid w\text{ has an odd number of }a\text{’s}\}$.

3. For $n\ge 1$, exactly half of the $2^n$ strings of length $n$ have an odd number of $a$'s. To see this, flip the first symbol between $a$ and $b$. This pairs each even-parity string with an odd-parity one. So the count is $2^{n-1}$.

4. For $n=0$, the empty string $\epsilon$ has zero $a$'s, so it is not in $L_1$. The count is $0$.

5. $n=1$: $1$; $n=2$: $2$; $n=3$: $4$; $n=4$: $8$.

6. Total $=0+1+2+4+8=15$.