4
$\begingroup$

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.

$\endgroup$
1
4
$\begingroup$

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}

$\endgroup$
3
  • $\begingroup$ 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)? $\endgroup$ – taylor.tackett Sep 20 '16 at 8:56
  • $\begingroup$ @taylor.tackett: It's an alternative, an OR and $^+$ means one or more: $a^+=aa^*$. $\endgroup$ – Markus Scheuer Sep 20 '16 at 8:59
  • $\begingroup$ @taylor.tackett: I've added some info which might be interesting. $\endgroup$ – Markus Scheuer Sep 20 '16 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.