# 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.

## 1 Answer

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}

• Thank you, great explanation. Does the pipe '|' operator indicate the phrase 'such that' or is it signifying an OR (or in my case, a union)? – taylor.tackett Sep 20 '16 at 8:56
• @taylor.tackett: It's an alternative, an OR and $^+$ means one or more: $a^+=aa^*$. – Markus Scheuer Sep 20 '16 at 8:59
• @taylor.tackett: I've added some info which might be interesting. – Markus Scheuer Sep 20 '16 at 11:40