8
$\begingroup$

I have a homework problem that is perplexing me because the math is beyond what I have done, although we were told that it was unnecessary to solve this mathematically. Just provide a close upper bound and justify it.

Let $$f(n) = |\{w ∈ \{a, b\}^n : aa \notin w \}|. $$ Provide an asymptotic upper bound on $f$ as $n\to\infty$.

So far: $$ \begin{array}{c|c|c} n & \text{strings} & \text{compared to } 2^n \\\hline 1 & 2 & 2^n - 0 \\ 2 & 3 & 2^n - 1 \\ 3 & 5 & 2^n - 3 \\ 4 & 8 & 2^n - 8 \\ 5 & 13 & 2^n - 18 \\ 6 & 21 & 2^n - 43 \\ \end{array} $$

The math that will give me an exact bound is beyond me. Obviously $O(2^n)$ is an upper bound, though it is not particularly tight.

Any suggestions on what I should try?

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Nov 16 '16 at 9:00
  • $\begingroup$ Many people would consider fib (n+1) as a perfectly fine expression for an upper bound. Even better as it is exact :-) $\endgroup$ – gnasher729 Nov 18 '16 at 11:37
8
$\begingroup$

So I'm not completely sure, but I think you're asking to count the number of strings of size $n$ (over the alphabet $\{a, b\}$) where the factor/substring $aa$ does not appear right?

In this case, there are a few combinatorial approaches that you can take. Both Yuval and ADG have given simpler and more intuitive arguments, so I definitely suggest checking their answers out! Here's one of my favorites, it's a little strange, but it's a very general (and kind of a fun) approach.

Let's start with a simpler language, that of words which starts and ends with $b$ (also with no substrings of $aa$). We can look at an admissible string (e.g. $bbb\textbf{a}b\textbf{a}bbbb$) as a list of sequences of $b$s separated by singular $a$s. This gives the construction: $$ w = (b^+a)^*b^+ $$ Now, how do we count sentences that belongs to this language?

Let's imagine that we're expanding these expressions out. What does $e^*$ denote? Well, it's simply $$ e^* = \epsilon \mid e \mid ee \mid eee \mid eeee \mid \dots $$ Now, this will make very little sense, but let's imagine that $e$ is a variable over some numerical field. In particular, we'll treat $\epsilon \to 1$, $a \mid b \to a + b$, and $abc \to a \times b \times c$. This then says that $$ e^* \to 1 + e + ee + eee + \dots $$ Let's try to see the motivation behind this strange interpretation. This is almost a bijective transformation. In particular, we want to preserve the count of each $e^n$ word, which, as you can readily see, we do. However, there's one crucial difference between the string expressions and numerical expressions: the multiplication (concatenation in strings, $\times$ in numerical expressions) is now commutative! Intuitively, commutativity lets us treat all permutations of the same word as the same; that is, we don't disambiguate between the expression $bbbab$ and $bbabb$; they both represent a string with 4 $b$s and one $a$. Therefore, this transformation allows us to preserve the count of each word of a certain number of $a$s and $b$s, but it now allows us to turn a blind eye on the superfluous details that we don't care about.

If you go back to precalculus, you might recognize this series as $\frac{1}{1 - e}$. I know that it doesn't make any sense to rewrite this regular expression as a numerically-valued function, but just bare with me for a moment.

Similarly, $e^+ = ee^* \to \frac{e}{1 - e}$. Which means that we can translate $w$ into $$ w \to \frac{1}{1 - (\frac{b}{1 - b} \times a)} \times \frac{b}{1 - b} $$

In turn, we can simplify this down to $$ w(a, b) = b \times \frac{1}{1 - (b + ba)} $$

This tells us that the language $w$ is isomorphic to the language $b(b \mid ab)^*$ (whose direct translation is already $\frac{b}{1 - b - ba}$) without ever having to resort to any language-theoretic tools! This is one of the power of treating these series as closed-form functions: we can perform simplifications on them that are nearly impossible to perform otherwise, hence reducing it down to a simpler problem.

Now, if you still recall any of your calculus course, you'll recall that certain types of functions (being well-behaving enough) admits these series representations known as Taylor expansions. Don't worry, we won't really have to worry about those pesky Calc 1 problem-sets; I'm just merely pointing out that these functions can be represented as the sum \begin{align*} w(a, b) &= \sum_{i,j} w_{ij} a^i b^j \end{align*} so that $w_{ij}$ gives the number of words that satisfies $w$ such that it has exactly $i$ occurrences of $a$ and $j$ occurrences of $b$. However, we don't particularly care about whether something is an $a$ or a $b$. Rather, we just care about the total number of characters in the string. To turn a "blind eye" between $a$ and $b$, we can just (literally) treat them the same, e.g. let $z = a = b$ and get $$ w(z) = w(z, z) = \frac{z}{1 - z - z^2} = \sum_k w_k z^k $$

where $w_k$ counts the number of satisfiable words of length $k$.

Now, all that's left to do is to find $w_k$. The usual combinatorial approach here would be to decompose this rational function into its partial-fraction: that is, given the denominator $1 - z - z^2 = (z - \phi)(z - \psi)$, we can rewrite $\frac{z}{(z - \phi)(z - \psi)} = \frac{A}{z - \phi} + \frac{B}{z - \psi}$ (There's a bit of algebra involved here, but this is a universal property of rational (one polynomial dividing another) functions). To solve this, you can refactor $$ \frac{A}{z - \phi} + \frac{B}{z - \psi} = \frac{z}{(z - \phi)(z - \psi)} $$ which generates the constraints $A + B = 1, A\psi + B\phi = 0$. Irregardless of what $A$ and $B$ are, recall that $\frac{1}{1 - x} = 1 + x + x^2 + \dots$, well, we can rearrange \begin{align*} w(z) &= \frac{-A}{\phi - z} + \frac{-B}{\psi - z} \\ &= (-A\phi)\frac{1}{1 - \frac{z}{\phi}} + (-B\psi) \frac{1}{1 - \frac{z}{\psi}} \\ &= (-A\phi)\left(1 + \phi^{-1} z + \phi^{-2} z^2 + \dots\right) + (-B\psi)\left(1 + \psi^{-1} z + \psi^{-2} z^2 + \dots\right) \end{align*} therefore $$ w_k = (-A\phi)\phi^{-k} + (-B\psi)\psi^{-k} $$ Here, $\phi$ is the golden ratio $\frac{1 + \sqrt{5}}{2}$ and $\psi = -\phi^{-1}$ is its conjugate. We then have an easy description of the asymptotic behavior of the $w$ language: it runs in $\Theta(\phi^n)$. In fact, if you expand everything out, you'll find that $$ w_k = \frac{\phi^{k} - \psi^{k}}{\sqrt{5}} = \left\lceil \frac{\phi^{k}}{\sqrt{5}} \right\rceil $$ There's also an intricate connection to another common combinatorial class. This is just the Fibonacci numbers!

Now, suppose you have $w_k$, which counts the number of strings of size $k$ that starts and ends with $k$ (and also contains no $aa$ substrings), how can we build a string that can start or end with an $a$? Well, it's simple: an admissible string is either in $w$ (starts and ends with $b$), or it is $a w$ (starts with $a$), or it is $w a$ (ends with $a$), or it is $a w a$ (starts and ends with $a$). Therefore: $$ f(n) = w_n + w_{n-2} + 2 * w_{n - 1} $$ Recall that $w_n$ is the fibonacci sequence, so $w_{n-1} + w_{n-2} = w_n$, which means that \begin{align*} f(n) &= (w_n + w_{n-1}) + (w_{n-2} + w_{n-1}) \\ &= w_{n+1} + w_{n} \\ &= w_{n+2} \end{align*} Therefore, $f(n) = \text{fib}(n + 2) = \left\lceil \frac{\phi^{n+2}}{\sqrt{5}} \right\rceil$

Now you probably don't have to do this analysis, but just by having the insight that this sequence is a shifted Fibonacci sequence ought to give you an idea of some other combinatorial interpretations that you can try.

$\endgroup$
7
$\begingroup$

Lee Gao's answer is excellent. Here is a different account. Consider the following automaton:

Automaton for the language

This is an unambiguous finite automaton (UFA) without $\epsilon$ transitions: an NFA such that each word has exactly one accepting path. The number of words of length $n$ is thus the number of paths of length $n$ from the starting state to an accepting state (since there are no $\epsilon$ transitions).

We can count the number of paths in a graph using linear algebra. Let $M$ be the transition matrix of the automaton: $M(q_i,q_j)$ is the number of arrows from $q_j$ to $q_i$ (each arrow is associated with a single symbol). Then $$ M^2(q_i,q_j) = \sum_k M(q_i,q_k) M(q_k,q_j), $$ which is exactly the number of paths of length 2 from $q_j$ to $q_i$. Similarly, $M^n(q_i,q_j)$ is the number of paths of length $n$ from $q_j$ to $q_i$. In our case, we want to count the number of paths of length $n$ from $q_0$ to $\{q_0,q_1\}$, and so $$ f(n) = \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix} \, . $$ The standard way to calculate such an expression is by diagonalizing $M$ (or, more generally, by computing the Jordan form of $M$). The eigenvalues of $M$ are easily calculated to be $\frac{1 \pm \sqrt{5}}{2}$, and so for some matrix $P$, $$ \begin{align*} f(n) &= \begin{pmatrix} 1 & 1 \end{pmatrix} P \begin{pmatrix} \left(\frac{1+\sqrt{5}}{2}\right)^n & 0 \\ 0 & \left(\frac{1-\sqrt{5}}{2}\right)^n \end{pmatrix} P^{-1} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\ &= A \left(\frac{1+\sqrt{5}}{2}\right)^n + B \left(\frac{1-\sqrt{5}}{2}\right)^n, \end{align*} $$ for some coefficients $A,B$. To determine $A,B$ we can either diagnoalize $M$ explicitly, or just set up a linear system using known values of $f$. Since $f(0) = 1$ and $f(1) = 2$, the latter approach shows that $$ A + B = 1 \\ \frac{1+\sqrt{5}}{2} A + \frac{1-\sqrt{5}}{2} B = 2 $$ Solving this system (e.g. using Gaussian elimination), we find out that $A = \frac{5+3\sqrt{5}}{10}$ and $B = \frac{5-3\sqrt{5}}{10}$. Therefore $$ \begin{align*} f(n) &= \frac{5+3\sqrt{5}}{10} \left(\frac{1+\sqrt{5}}{2}\right)^n + \frac{5-3\sqrt{5}}{10} \left(\frac{1-\sqrt{5}}{2}\right)^n \\ &= \Theta(\lambda_{\max}^n), \text{ where } \lambda_{\max} = \frac{1+\sqrt{5}}{2}. \end{align*} $$ The same approach works for every regular language.

$\endgroup$
  • $\begingroup$ This is a fun approach! I always love seeing linear algebraic reductions for path related problems :) $\endgroup$ – Lee Nov 16 '16 at 17:42
4
$\begingroup$

@Lee Gao's is too complex (I haven't even read the whole thing), here is a simplistic approach:

Let f(n) be all desired strings out of which let a(n) be strings that end at a and b(n) be strings that end at b.

Now for every string that ends at b we can directly add a to get ba in ending and a valid string: $$a(n)=b(n-1)\tag{1}$$ Note than we cannot add a to end of strings that end at a otherwise we will have aa at the end.

We can add b to any string: $$b(n)=a(n-1)+b(n-1)\tag{2}$$

Now $n\mapsto n-1$ in $(1)$ and substitue in $(2)$: $$b(n)=b(n-2)+b(n-1)$$ So b(n) is fib(n) and since a(n) is b(n-1) hence a(n) is fib(n-1). Now f(n) is: $$f(n)=a(n)+b(n)={\rm fib}(n)+{\rm fib}(n-1)={\rm fib}(n+1)$$ As fib(n) is $(\varphi^n-\varphi^{-n})/\sqrt{5}$, hence f(n) is ${\rm O}(\varphi^n)$, $\varphi=\frac{1+\sqrt{5}}{2} \approx 1.618$. (Taking $\varphi/\sqrt5$ as constant and neglecting $\varphi^{-n}$ for large $n$ to get an asymptote)

Note: fib(0)=0, fib(1)=1.

$\endgroup$
  • $\begingroup$ Your upper bound isn't very good, however: every language over $\{a,b\}$ has at most $2^n$ words of length $n$! $\endgroup$ – Yuval Filmus Nov 16 '16 at 7:32
  • $\begingroup$ @YuvalFilmus what's the problem, you want a closer bound then use ${\rm fib}(n)=(\phi^n-\phi^{-n})/\sqrt{5}$ $\endgroup$ – RE60K Nov 16 '16 at 7:50
  • $\begingroup$ This is great! The pairs lock-step inductive constructions of $a$ and $b$ was what I was thinking of as well. $\endgroup$ – Lee Nov 16 '16 at 17:37

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.