2
$\begingroup$

Let $A$ be a finite alphabet with $|A|=a$, let $S$ be a (not neccesarily finite) set of non-empty words in the free monoid $A^*$ such that $S$ generates a free monoid of $A^*$. Prove that $$\sum\limits_{w\in S}\frac{1}{a^{l(w)}}\leq 1$$ where $l(w)$ is the length of word $w$.

  • 0
    You need to formulate more carefully. You want $S$ to be independent, to freely generate a free monoid so to speak. If not, you can just take $S=A^*$, which certainly generates the free monoid $A^*$, for a counterexample.2012-11-18
  • 1
    Assuming that $S$ is intended to be the minimal generating set of $S^*$, $S$ is a code, and this is the [Kraft inequality](http://en.wikipedia.org/wiki/Kraft%27s_inequality). (The link gives only the finite case, but the countably infinite case is a consequence.)2012-11-18

1 Answers 1