# Maximal prefix codes and maximal length

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?

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

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.
• 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?
• 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$. Mar 11, 2021 at 12:34