0
$\begingroup$

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

enter image description here

enter image description here

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

enter image description here

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.

$\endgroup$

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Why not use the OP's notation for empty string ($\lambda$)? (+1 for the comment on $\lambda \notin C$.) $\endgroup$
    – copper.hat
    Jan 30, 2020 at 19:33
  • $\begingroup$ @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$. $\endgroup$
    – J.-E. Pin
    Jan 30, 2020 at 23:25
  • $\begingroup$ Perhaps, but I have never seen the group identity (why not $e$?) used in this context. $\endgroup$
    – copper.hat
    Jan 30, 2020 at 23:40
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Red Banana
    Jan 30, 2020 at 4:51
  • $\begingroup$ Yes, the length of the string. $\endgroup$
    – copper.hat
    Jan 30, 2020 at 4:52
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Red Banana
    Jan 30, 2020 at 5:27
  • 1
    $\begingroup$ That seems a little bit roundabout to me, but if you're happy with it so am I. $\endgroup$
    – MJD
    Jan 30, 2020 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.