2
$\begingroup$

I need to find a way to iterate over all sequences of words in two letters $A,B$ avoiding the sequence $A^2 = AA$ and $B^3 = BBB$. First of all, what is the regular expression for such a thing?

I need a way of iterating over all such possible words. I tried this one: $$ w \mapsto \{ wA, wB, wBB\} $$

however, if I run this function again, we obtain: $$ w \mapsto \{ wAA,wAB,wABB,wBA,wBB,wBBB,\dots \}$$ and you can see we have obtained the expressions we are trying to avoid.

I need way of generating all the words in $\{A,B\}$ of length $n$ avoiding these two patterns.

$\endgroup$
  • 1
    $\begingroup$ The observation and explanation in Yuval's answer might be helpful. $(A+B)^* = (A^+ B^+)^* A^* + (B^+ A^+)^* B^*$. Follow the hint and replace $A^+$ and $B^+$ by powers up to 2 and 3 respectively. $\endgroup$ – Hendrik Jan Apr 4 '18 at 12:52
3
$\begingroup$

Instead of constructing a regular expression, it is better to construct a DFA, or rather, a DFA with some "missing transitions". The DFA has the following states:

  • $q_0$: initial state.
  • $q_A$: state after seeing one A.
  • $q_B$: state after seeing one B.
  • $q_{BB}$: state after seeing two Bs.

The transition function is $$ \begin{array}{c|cccc} & q_0 & q_A & q_B & q_{BB} \\\hline q_0 & & A & B & \\ q_A & & & B & \\ q_B & & A & & B \\ q_{BB} & & A & & \end{array} $$ This is read as follows: when at row $q$, upon reading $\sigma$, move to the appropriate column, if any. If there is no appropriate column, we have reached the (invisible) sink state.

Using this, it is not hard to see that the number of words of length $n$ in your language is $$ \begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}. $$ Calculation shows that for $n \geq 1$, the number of words of length $n$ in your language is $$ \mathrm{round}(C \lambda^n), \text{where } C \approx 1.678735602594163 \text{ and } \lambda \approx 1.324717957244746. $$ The eigenvalue $\lambda$ is also the unique real root of $x^3-x-1$.

A glance at the OEIS reveals that your sequence is A164001, and has the recurrence $$ a_n = \begin{cases} n+1 & n \leq 3, \\ a_{n-2} + a_{n-3} & n \geq 4. \end{cases} $$ (The recurrence $a_n = a_{n-2} + a_{n-3}$ is of course related to the polynomial $x^3-x-1$ above.)

$\endgroup$
  • $\begingroup$ oh wow that's the Plastic Number. $\endgroup$ – john mangual Apr 4 '18 at 13:07
  • 1
    $\begingroup$ @Yuval The recurrence is also implicit following your answer for finding a regular expression with bounded length segments $A$ and $B$. We return to a smaller case by scrapping a factor $(AB+ABB)$ or $(BA+BBA)$ respectively. $\endgroup$ – Hendrik Jan Apr 4 '18 at 13:32
  • $\begingroup$ @HendrikJan Nice! This way you can find $\lambda$. Can you also determine $C$ this way? $\endgroup$ – Yuval Filmus Apr 4 '18 at 14:25

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.