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?

Improve this question
$\endgroup$
7
  • $\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
    Commented Apr 5, 2018 at 19:03
  • $\begingroup$ @quicksort so $pipo$ would be 4 letters then right? $\endgroup$
    – Diceble
    Commented Apr 5, 2018 at 19:10
  • $\begingroup$ @quicksort and after thinking i would have no idea how to count that... $\endgroup$
    – Diceble
    Commented Apr 5, 2018 at 19:15
  • $\begingroup$ How many strings of length $n$ made of zeroes and ones are there? $\endgroup$
    – quicksort
    Commented Apr 5, 2018 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
    Commented Apr 5, 2018 at 19:34

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.