# Proving that Every Full Prefix-Free Language is Maximal

I'm practicing a problem where I need to prove that every full prefix-free language is maximal.

I know a prefix-free language A is maximal if it is not a proper subset of any prefix-free language, where a prefix-free language is full if,

$$\sum_{x\in A} 2^{-|x|} = 1$$

Furthermore, I know that a language A ⊆ {0, 1}* is prefix-free if no element of A is a prefix of any other element of A and that the Kraft inequality says that for every prefix-free language A,

$$\sum_{x\in A} 2^{-|x|} \leqslant 1$$

I'm pretty sure that a full prefix free language is maximal, since it belongs to the maximal prefix-free set. I don't know, however, how to formally prove this. Should I be doing induction with Kraft's Inequality and with what I know about the relationship between maximal and prefix-free sets?

Any help would be appreciated!

Suppose that $$A$$ is a full prefix-free language, that is, $$\sum_{x \in A} 2^{-|x|} = 1.$$ Assume, for the sake of contradiction, that $$A$$ is not maximal. Then there is a word $$y$$ such that $$A \cup \{y\}$$ is also prefix-free. According to Kraft's inequality, $$\sum_{x \in A \cup \{y\}} 2^{-|x|} \leq 1.$$ However, this implies that $$1 \geq \sum_{x \in A} 2^{-|x|} + 2^{-|y|} = 1 + 2^{-|y|} > 1,$$ and so we reach a contradiction. This shows that $$A$$ is maximal.

The more interesting direction is the converse: if $$A$$ is maximal then $$A$$ is full. Let me give two proofs of this fact.

The first proof is by induction on the length of the maximal word in $$A$$ (note that if $$A$$ is maximal then it cannot be empty). If $$A = \{\epsilon\}$$ then $$A$$ is indeed full. Now suppose that $$A$$ contains some word of positive length. Since $$A$$ is prefix-free, $$\epsilon \notin A$$. Hence we can write $$A = \{ 0x : x \in A_0 \} \cup \{ 1x : x \in A_1 \},$$ where $$A_0,A_1$$ are prefix-free, and have shorter maximal words. It is easy to check that $$A_0,A_1$$ are maximal: for example, if $$A_0 \cup \{y\}$$ were prefix-free, then $$A \cup \{0y\}$$ would be prefix-free. Applying the induction hypothesis, we see that $$\sum_{x \in A} 2^{-|x|} = \sum_{x \in A_0} 2^{-|0x|} + \sum_{x \in A_1} 2^{-|1x|} = \frac{1}{2} \sum_{x \in A_0} 2^{-|x|} + \frac{1}{2} \sum_{x \in A_1} 2^{-|x|} = \frac{1}{2} + \frac{1}{2} = 1.$$

The second proof uses a probabilistic argument, though for the sake of presentation I will present it as a counting argument. Let $$A$$ be a prefix-free code which is not maximal, and let $$n$$ be the length of the maximal word in $$A$$. For a word $$x$$ of length at most $$n$$, let $$B_n(x)$$ denote all words of length $$n$$ of which $$x$$ is a prefix, and note that $$|B_n(x)| = 2^{n-|x|}$$. Since $$A$$ is prefix-free, the sets $$B_n(x)$$ for $$x \in A$$ are all disjoint. Therefore $$\left| \bigcup_{x \in A} B_n(x) \right| = \sum_{x \in A} |B_n(x)| = \sum_{x \in A} 2^{n-|x|} = 2^n \sum_{x \in A} 2^{-|x|} < 2^n.$$ Therefore there is some word $$w$$ of length $$n$$ which has no word in $$A$$ as a prefix. So $$A \cup \{w\}$$ is also prefix-free, and we conclude that $$A$$ is not maximal.

Both proofs we presented above actually show the following stronger fact: every prefix-free code is a subset of a maximal prefix-free code. Let me quickly outline how to obtain this result using both proofs.

In the first proof, we prove the claim by induction. If $$A = \emptyset$$ then we can extend it to $$A = \{\epsilon\}$$, and if $$A = \{\epsilon\}$$ then $$A$$ is already maximal. So suppose that $$A = 0A_0 \cup 1A_1$$. The induction hypothesis shows how to extend $$A_0,A_1$$ to maximal prefix-free codes $$B_0,B_1$$ (respectively), and then $$B = 0B_0 \cup 1B_1$$ is maximal.

In the second proof, we obtain a maximal prefix-free code by adding to $$A$$ all words in $$\overline{\bigcup_{x \in A} B_n(x)}.$$

In both proofs, one way to check that the extended code is maximal is by verifying that it is full.

For extra credit, the reader can try extending the ideas above to infinite prefix-free codes, that is, prefix-free codes containing countably many words.

• Nice exposition. Feb 8, 2019 at 5:36

It looks like, I am afraid, you have done little useful thinking after a lot of typing. Well, that does happen a lot to me as well when it is about a new field.

Let $$A$$ be a full prefix-free language over alphabet $$\{0,1\}$$, i.e., $$\sum_{x\in A} 2^{-|x|} = 1\,.$$

For the sake of contradiction, assume $$A$$ is not maximal. That is, there exists a word $$y\not\in A$$ such that $$B=A\cup\{y\}$$ is a prefix-free language. Then

$$\sum_{x\in B} 2^{-|x|} = 2^{-|y|} + \sum_{x\in A} 2^{-|x|} = 2^{-|y|} + 1 >1\,,$$ which contradicts the Kraft inequality.

Done.

Here are several related exercises. Note the alphabet is assumed to be finite.

Exercise 1. Show that a full prefix-free language over any alphabet must be maximal.

Exercise 2. Show that a maximal prefix-free finite language over any alphabet must be full.

Exercise 3. Show that a maximal prefix-free infinite language over any alphabet must be full.