String in an kleene star alphabet

Question

Let Σ = {a, b}. How many strings of length 10 are in the language (bb + aab)*?

If this a matter of writing them out or is there a formula to it?

Answer 1

We could also associate a geometric series with $$(bb+aab)^\star=\varepsilon+(bb+abb)+(bb+abb)^2+\ldots$$ Since each word in this language is uniquely identified by the occurrences of $bb$ and $aab$ parts and since we are only interested in the length of the substrings $bb$ and $aab$, we consider the series \begin{align*} \frac{1}{1-(x^2+x^3)}=1+(x^2+x^3)+(x^2+x^3)^2+\ldots \end{align*} and calculate the coefficient of $x^{10}$ of this series:

\begin{align*} [x^{10}]\frac{1}{1-x^2(1+x^3)}&=[x^{10}]\sum_{k=0}^{\infty}x^{2k}(1+x)^k\\ &=[x^{10}]\sum_{k=4}^5x^{2k}(1+x)^k\\ &=\sum_{k=4}^{5}[x^{10-2k}](1+x)^k\\ &=\binom{5}{2}+\binom{5}{0}\\ \end{align*}

In short: We have $\binom{5}{0}=1$ possibilities to generate a word of length $10$ with the string $bb$ \begin{align*} (bb)(bb)(bb)(bb)(bb) \end{align*}

Next we can replace two strings $abb$ with three of $bb$ giving $\binom{5}{2}$ and there are no further possibilities.

Answer 2

You can write down a recurrence to solve this: If $a_n$ means the set of strings of length $n$ in the language, then we have $$ a_n=a_{n-2}+a_{n-3}, \qquad a_0=1, a_1=0, a_2=1 $$ Fully solving the recurrence would be overkill when all you're interested in is finding $a_{10}$, but it should be fairly quick to compute $a_3, a_4, \ldots, a_8$ and then $a_{10}$.