# Find the number of words in a language of given length

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?

• Please check that I understood your question correctly. – Yuval Filmus Feb 19 '16 at 12:27
• 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? – Raphael Feb 19 '16 at 12:53
• 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? – Fred Feb 21 '16 at 11:59
• 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). – vonbrand Feb 21 '16 at 17:41

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.

• 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.) – Raphael Feb 19 '16 at 12:56
• Thanks, your solution is indeed better since it can accommodate NFAs. – Yuval Filmus Feb 19 '16 at 13:00
• 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. – Fred Feb 21 '16 at 12:01