# 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 $\sum$ {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 substrings {a, b} = $\sum^*$ (where {a, b} = $\sum$) where the strings found in $\sum^*$ do not contain the substring aaa.

Any advice on how to generate the regular-expression that will define this language would be helpful.

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)

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.
• @taylor.tackett: It's an alternative, an OR and $^+$ means one or more: $a^+=aa^*$. – Markus Scheuer Sep 20 '16 at 8:59