Let $X$ a maximal prefix code on an alphabet $A$, $m(X)$ its maximal length, $F = X \cap A^{m(X)}$ and $F’ \subseteq A^{m(X)}$. Let $X’ = X \setminus F \cup F’$ a maximal prefix code. Why is it true that $X’ = X$? In other words, why is it true that one cannot obtain a maximal prefix code from another maximal prefix code with same maximal length by changing only the words of maximal length? Any reference for this result?

  • $\begingroup$ math.stackexchange.com/q/4041816/14578 $\endgroup$
    – D.W.
    Mar 9, 2021 at 20:11
  • $\begingroup$ Yes, I asked the same question on math.stackexchange but I realised it would have been more appropriate to ask here :) $\endgroup$
    – Cat
    Mar 10, 2021 at 9:03

1 Answer 1


I'll assume that a prefix code is a set of words in which no word is the prefix of any other, and "maximal" means it is impossible to add any word to the set and keep this property.

Let $w$ be a maximal-length word that is not in $X$. There are two possibilities:

  • At least one (shorter) word in $X \setminus F$ is a prefix of $w$, in which case we could not add $w$ even if we first remove all words in $F$ from $X$;
  • No (shorter) word in $X \setminus F$ is a prefix of $w$, in which case we could add $w$ to $X$ without needing to first remove any words in $F$, contradicting the assumption that $X$ is maximal.
  • $\begingroup$ Thank you. I have a few questions: are you considering $w$ in $X’$? If so, we would not need to consider the first possibility, since $X’$ is also prefix, thus no word of $X’$ could be a prefix of $w$, which is also in $X’$. Is that correct? $\endgroup$
    – Cat
    Mar 11, 2021 at 9:37
  • $\begingroup$ I don't follow. "$X'$ is also prefix" -- $X'$ is a set of words, so I don't understand what you mean by calling it "prefix". A word $x$ is a prefix of a word $y$ if $y=xz$ for some (possibly empty) word $z$. $\endgroup$ Mar 11, 2021 at 12:34

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.