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$.
Free monoids, length of a word $w$
2
$\begingroup$
monoid
-
1Assuming 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
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
J. Berstel, D. Perrin and C. Reutenauer, Codes and automata. Encyclopedia of Mathematics and its Applications, 129. Cambridge University Press, Cambridge, 2010. xiv+619 pp. ISBN: 978-0-521-88831-8.