2
$\begingroup$

I was asked the following question:

Consider the language $S^*$, where $S = \{ab, ba\}$, write out all the words that have seven or fewer letters?

How do I go about calculating the number of words? Are there any resources that break this down to the most basic level?

$\endgroup$
  • 1
    $\begingroup$ Please check that I understood your question correctly. $\endgroup$ – Yuval Filmus Feb 19 '16 at 12:27
  • 3
    $\begingroup$ The question does not ask you what you suggest in the title; you are merely asked to enumerate nine words. What have you tried and where did you get stuck? Have you checked your understanding of the Kleene star operator? $\endgroup$ – Raphael Feb 19 '16 at 12:53
  • $\begingroup$ My understanding of Kleene star is that it's used to create all possible string concatenations of the language. I assume enumeration would be the best possible option for a question like this? $\endgroup$ – Fred Feb 21 '16 at 11:59
  • $\begingroup$ Unless the resulting language has some specially simple structure, there is no other way. Rejoice, you weren't asked to check how many of length 200 there are (there are $2^{100}$ of them). $\endgroup$ – vonbrand Feb 21 '16 at 17:41
2
$\begingroup$

You can solve the general problem using linear algebra. First, construct a DFA for the language $S^*$. Then, describe its transition function in matrix form: if the state space is $Q$, construct a $Q \times Q$ matrix $A$ in which $A(s_1,s_2)$ is the number of letters that would cause a transition from $s_1$ to $s_2$. If $s$ is the starting state, let $1_s$ be the corresponding vector, and let $j$ be the all-one vector. The number of words of length exactly $n$ is $1_s A^n j$ (or perhaps $j A^n 1_s$ if I mixed things up). You can use the spectral decomposition of $A$ to get a formula, or you can calculate it quickly using repeated squaring.

That is the general theory. In your case, it's not too hard to enumerate all words of length up to $7$ by hand. I challenge you to do that.

$\endgroup$
  • 1
    $\begingroup$ This does not seem what the OP wants; I suspect they misunderstood what they were asked. Anyway, this is unnecessarily complicated for just getting the count for a fixed $n$; this approach is more powerful and involves far less calculations, at least for moderately large $n$. (I know you know that, leaving the reference for readers' benefits.) $\endgroup$ – Raphael Feb 19 '16 at 12:56
  • $\begingroup$ Thanks, your solution is indeed better since it can accommodate NFAs. $\endgroup$ – Yuval Filmus Feb 19 '16 at 13:00
  • $\begingroup$ Thank you all for your answers and input. This is still a bit overly complex for me. The textbook we're using doesn't define DFA's till a few chapters later. As mentioned in my comment above, enumeration is possibly the best way to this than to find a formulaic approach this early on. $\endgroup$ – Fred Feb 21 '16 at 12:01

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.