# Free monoids, length of a word $w$

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

-
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. – Marc van Leeuwen Nov 18 '12 at 9:54
Assuming that $S$ is intended to be the minimal generating set of $S^*$, $S$ is a code, and this is the Kraft inequality. (The link gives only the finite case, but the countably infinite case is a consequence.) – Brian M. Scott Nov 18 '12 at 10:16

As pointed out by Brian Scott, this is the Kraft inequality (more precisely the Kraft-McMillan theorem in your case since you don't assume that $S$ is prefix). For a proof of the general case and an interesting extension to Bernoulli distributions, see Chapter 2 in