Finding the set of strings over $\{a, b\}$ that do not contain the substring aaa 

I need to identify the set of all possible strings over $\Sigma = \{a, b\}$ that do not contain the substring $aaa$.


I have becoming more familiar with regular-language and languages explored in Automata Theory, and have been defining a particular language through regular-expressions.


I am having a hard time trying to find the set of strings of $\Sigma^*$ (where $\Sigma = \{a, b\}$) that do not contain the substring aaa.


Any advice on how to generate the regular-expression that will define this language would be helpful.
 A: We can describe the set of valid strings as the strings built from the alphabet $V=\{a,b\}$ which contain at most one or two consecutive $a$'s.

These are strings
  
  
*
  
*starting with zero or more $b$'s:$$b^*$$
  
*followed by zero or more occurrences of $a$ or $aa$ each followed by one or more $b$'s: $$(ab^+|aab^+)^*$$
  
*and terminating with zero, one or two $a$'s
  $$(\varepsilon|a|aa)$$
We obtain
\begin{align*}b^*(ab^+|aab^+)^*(\varepsilon|a|aa)\tag{1}\end{align*}

$$ $$

Add-on: The regular expression (1) generates all valid words in a unique manner. In such cases we can use it to derive a generating function $$A(z)=\sum_{n=0}^\infty a_n z^n$$ with
  $a_n$ giving the number of valid words of length $n$.

In order to do so all we need to know is the geometric series expansion since the $star$ operator
\begin{align*}
a^*=\left(\varepsilon|a|a^2|a^3|\cdots\right)\qquad\text{ translates to }\qquad 1+a+a^2+a^3+\cdots=\frac{1}{1-a}
\end{align*}
Accordingly $a^+=aa^*$ translates to $\frac{a}{1-a}$ and alternatives like $(\varepsilon|a|aa)$ can be written as $1+a+a^2$.

We obtain by translating the regular expression in the language of generating functions (and by mixing up somewhat the symbolic to provide some intermediate steps)
\begin{align*}
b^*\left(ab^+|aab^+\right)^*(\varepsilon|a|aa)
&\longrightarrow \quad \frac{1}{1-z}\left(\left.\frac{z^2}{1-z}\right|\frac{z^3}{1-z}\right)^*\left(1+z+z^2\right)\\
&\longrightarrow \quad \frac{1}{1-z}\left(\frac{z^2+z^3}{1-z}\right)^*(1+z+z^2)\\
&\longrightarrow \quad \frac{1}{1-z}\cdot\frac{1}{1-\frac{z^2+z^3}{1-z}}(1+z+z^2)\\
&\quad\quad=\frac{1+z+z^2}{1-z-z^2-z^3}
\end{align*}
We conclude: The number of valid words is given by the generating function $A(z)$
  \begin{align*}
A(z)&=\frac{1+z+z^2}{1-z-z^2-z^3}\\
&=1+2z+4z^2+7z^3+13z^4+\color{blue}{24}z^5+44z^6+81z^7+\cdots
\end{align*}
The expansion was done with the help of Wolfram Alpha. We see that e.g. the number of valid words of length $5$ is $24$.

So, out of $2^5=32$ binary words of length $5$ there are $8$ invalid words marked blue in the table below.
\begin{array}{cccc}
\color{blue}{aaaaa}\qquad&ab\color{blue}{aaa}\qquad&ba\color{blue}{aaa}\qquad&bb\color{blue}{aaa}\\
\color{blue}{aaaa}b\qquad&abaab\qquad&b\color{blue}{aaa}b\qquad&bbaab\\
\color{blue}{aaa}ba\qquad&ababa\qquad&baaba\qquad&bbaba\\
\color{blue}{aaa}bb\qquad&ababb\qquad&baabb\qquad&bbabb\\
aabaa\qquad&abbaa\qquad&babaa\qquad&bbbaa\\
aabab\qquad&abbab\qquad&babab\qquad&bbbab\\
aabba\qquad&abbba\qquad&babba\qquad&bbbba\\
aabbb\qquad&abbbb\qquad&babbb\qquad&bbbbb\\
\end{array}
