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

  • 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

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.