# Proving that if $C$ is a prefix code then it is uniquely decipherable?

I'm reading James Anderson's Automata Theory with Modern Applications. Here:

And I tried to prove the following theorem (for prefix codes).

I tried in the following way: Suppose $$C$$ is a prefix code which is not uniquely decipherable, that is there is a string $$u \in C$$ with two different expressions $$u=ab=cd$$. But $$u=vw$$ and hence $$vw=ab=cd$$ where $$w= \lambda$$ and $$\lambda$$ is the empty word, therefore $$v=a=c$$ and $$\lambda=b=d$$ which contradicts your hypothesis that $$u$$ is not uniquely decipherable.

Is this correct? I am confused because I paired $$v=a=c$$ and $$\lambda=b=d$$ and I'm not sure if that is valid.

Let $$1$$ be the empty word. First of all, one needs to discard the case $$C = \{1\}$$ for the result to be correct. Indeed, if $$C = \{1\}$$, then $$C$$ is a prefix code, but $$C^*$$ is not a free monoid.

Let now $$C$$ be a nonempty prefix code such that $$C \not= \{1\}$$. Then $$C$$ does not contain $$1$$, since $$1$$ is a prefix of every word. Let $$w$$ be a word of minimal length having two $$C$$-factorizations $$w = c_1 \dotsm c_n = c'_1 \dotsm c'_m$$ Both $$c_1$$ and $$c'_1$$ are nonempty words and since $$w$$ has minimal length, $$c_1 ≠ c'_1$$. Thus either $$c_1$$ is a prefix of $$c'_1$$, or the other way around. Contradiction.

• Why not use the OP's notation for empty string ($\lambda$)? (+1 for the comment on $\lambda \notin C$.) Jan 30, 2020 at 19:33
• @copper-hat The notation $\lambda$ (or $\epsilon$) for the empty word was introduced by computer scientists because they often work with the binary alphabet $\{0, 1\}$. But otherwise, especially on a mathematical forum, it is more natural to stick with the standard notation of the identity of a monoid (or a group), which is $1$. Jan 30, 2020 at 23:25
• Perhaps, but I have never seen the group identity (why not $e$?) used in this context. Jan 30, 2020 at 23:40

It might be easier to do an inductive proof on the number of code symbols in two words.

Suppose $$C$$ is a prefix code for $$S$$.

I use $$|s|$$ for the length (in terms of $$\Sigma$$) of $$s$$.

Choose $$s \in S$$ and write $$s=c_1 t_1 = c_2 t_2$$ where $$c_k \in C$$ and $$t_k \in C^*$$. Suppose $$|c_1| \le |c_2|$$ and write $$s= c_1 w t_1'$$, where $$|w| = |c_2|-|c_1|$$ and $$t_1 = w t_1'$$. Then $$c_1w = c_2$$ and hence $$c_1 = c_2$$ and $$w = \lambda$$. Now repeat with $$t_1, t_2$$.

• What is the meaning of $|c_1| \leq |c_2|$? Until now I didn't see this notation in the book. Is it string length? Jan 30, 2020 at 4:51
• Yes, the length of the string. Jan 30, 2020 at 4:52

If $$ab=cd$$, and $$a≠c$$, then one of $$a$$ and $$c$$ is shorter and one is longer. The shorter is a prefix of the longer, therefore the code is not a prefix code.

• In this case, we're assuming $C$ is a prefix code and the elements of $C$ are not uniquely decipherable and obtaining a contradiction to our assumption that $C$ is a prefix code, right? Jan 30, 2020 at 5:27
• That seems a little bit roundabout to me, but if you're happy with it so am I.
– MJD
Jan 30, 2020 at 5:33