1
$\begingroup$

I have a language $L^*$ for $L = \{pi,po\}$ (I think pi counts as one letter and po also as one letter otherwise a max length of 9 is not possible).

The question is how many words I can make with $L^*$ where the maximum length is 9.

The answer is 31, but I do not know how it got calculated. How is this calculated?

$\endgroup$
  • $\begingroup$ Both $pi$ and $po$ count as two letters for the answer to be correct. Can you count how many strings of length $n$ you can form? $\endgroup$ – quicksort Apr 5 '18 at 19:03
  • $\begingroup$ @quicksort so $pipo$ would be 4 letters then right? $\endgroup$ – Diceble Apr 5 '18 at 19:10
  • $\begingroup$ @quicksort and after thinking i would have no idea how to count that... $\endgroup$ – Diceble Apr 5 '18 at 19:15
  • $\begingroup$ How many strings of length $n$ made of zeroes and ones are there? $\endgroup$ – quicksort Apr 5 '18 at 19:22
  • $\begingroup$ is it 2^n ? sorry if I'm totally wrong, but I just miss something where i proberly would facepalm myself if I found it out. $\endgroup$ – Diceble Apr 5 '18 at 19:34
1
$\begingroup$

Here are all words in $L^*$ of length at most 9: $$ \epsilon, \\ pi, po, \\ pipi, pipo, popi, popo, \\ pipipi, pipipo, pipopi, pipopo, popipi, popipo, popopi, popopo, \\ pipipipi, pipipipo, pipipopi, pipipopo, pipopipi, pipopipo, pipopopi, pipopopo, popipipi, popipipo, popipopi, popipopo, popopipi, popopipo, popopopi, popopopo. $$ In total, there are 31 words.

More generally, suppose that we have $m$ distinct words of length $\ell$. Then the total number of words of length at most $n$ is $$ \sum_{r=0}^{\lfloor n/\ell \rfloor} m^r = \frac{m^{\lfloor n/\ell \rfloor+1}-1}{m-1}. $$ In our case, we get $\frac{2^{\lfloor 9/2 \rfloor + 1}-1}{2-1} = 2^{4+1}-1 = 31$.

$\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.