String in an kleene star alphabet 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?
 A: 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.
A: 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}$.
