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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.