  To fix ideas, it is useful to have an example of a prefix-free encoding in mind. Suppose we have a string \(\sigma =x_1 \ldots x_k\) of length \(k\). This is the initial part of the string \(\sigma 1\), so if any string was an acceptable input, we would not have a prefix-free encoding. But if the code contained information about the length of the string encoded, we would know that the length of \(\sigma , k\), is less than the length of \(\sigma 1\). We can make this idea precise as follows (using a code similar to that used to a different end in the  proof  of Theorem  4). Let the code of \(\sigma\) be the string \(1^{[\lvert\sigma\rvert]}0\sigma\)—that is, the code of a string consists of a representation of the length of the string, followed by a 0, followed by the string. This is clearly a prefix-free  encoding.[12]  This coding is not particularly efficient, but more compact prefix-free encodings do exist.