2
$\begingroup$

I am studying a distance CS course, but there is no tutor available, so I would appreciate your help...

Consider the language $S = \{a, aa, ab\}$ How many distinct words of length $n$ will appear in $S^*$?

Is there a way to do this without having to "enumerate" $S^*$ until the answer is found?

$\endgroup$
1
$\begingroup$

D.W. has shown how to solve the problem in a general setting. Let me show the simplest way for this particular problem.

What is $S^*$?

$S^*=\{w\in\{a,b\}^*: w\text{ does not contain }bb\text{ and }w \text{ does not start with } b\}$.

The description above can be shown, for example, by demonstrating that the right hand side contains $\epsilon, a, aa, ab$ and its concatenation with itself.

Recurrence relation

Let $f_n$ be the number of words of length $n$ in $S^*$. Then $f_0=1$ and $f_1=1$.

Let $w$ be a word of length $n+1$, $n\ge1$.

  • $w$ ends with $a$. Then $w=xa$ for $x\in S^*$ of length $n$.
  • Otherwise, $w$ ends with $b$. Then $w=yab$ for $y\in S^*$ of length $n-1$.

The above shows that $f_{n+1}=f_n+f_{n-1}$. So $f_n$ is the famous Fibonacci sequence.

Final formula

$$f_n=\frac{\left(\dfrac{1+\sqrt5}2\right)^n-\left(\dfrac{1-\sqrt5}2\right)^n}{\sqrt5}$$


Exercise. (One minute or less if you find the shortcut.) How many distinct words of length $n$ appear in $\{a,bb\}^*$?

$\endgroup$
  • 1
    $\begingroup$ Thanks for the comprehensive reply. Based on this I can now easily determine that there should be 13 words of length 6. Its sad that the course book asks these type of questions but lacks any example of this method. I played around a bit and wrote some code that produced all the new generated words in S* I also checked out discrete.openmathbooks.org/dmoi2/sec_recurrence.html $\endgroup$ – mikey3433 Mar 8 at 19:42
  • 1
    $\begingroup$ I decided to try S={a b cc}. it turns out that we can get the count of the number of items of length n in S* by: Xn = f(n-1) + f(n-2) f(n) = Xn+f(n-1) Hence f(n) = 2*f(n-1)+f(n-2) $\endgroup$ – mikey3433 Mar 8 at 21:39
1
$\begingroup$

The language $S^*$ is regular. Therefore, it can be expressed by a DFA. Now use Why isn't it simple to count the number of words in a regular language? or https://cstheory.stackexchange.com/q/8200/5038.

$\endgroup$

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.