Binary Strings: How to determine if decomposition is ambiguous

Question

Let's say I have the following decomposition:

$$\{100,10011,00110\}^*$$

How would I determine if the decomposition is ambiguous or unambiguous?

Answer 1

Let $L_0 = \{100, 10011, 00110\}$, and let $L= L_0^{*}$. Then $L$ is unambiguous:

By induction on length of $w\in L$, we show that $w$ has a unique decomposition into $100, 10011, 00110$.

Base case: $|w| \le 5$. Then $w$ cannot be of the form $xy$ for $x,y\in L_0$, otherwise its length would be at least 6.

If $w=\varepsilon$ then the result is trivially true.

Case 0: $w$ begins with $0$. Then $w = 00110$, and there is no other possibility.

Case 1: $w$ begins with $1$. Then we must have either $w = 100$ or $w=10011$, as there are no other possibilities.

Induction step: Assume the induction hypothesis (IH) that the result holds for strings of length less than $|w|$, and $|w| > 5$. Then $w = xy$ for some $x\in L_0$ and $y\in L$.

Case 1: $w$ begins with $1$. Then $w = 100 u y$, where $x = 100 u$ ($u$ might be empty$. Three subcases:

• If $uy$ begins with $11$, then $x = $10011$; * if $uy$ begins with $10$, then $x = $100$;
• if $uy$ begins with $0$, then $x = $100$.

In each subcase, $x$ is uniquely determined. By IH, $y$ has a unique decomposition. Hence so does $w = xy$.

Case 0: $w$ begins with $0$. Then we must have $w = 00110 y$, and it's easy to see that there is no other way to decompose $00110$. Thus $y\in L$, so by IH $y$ has a unique decomposition, thus $w=00110 y$ does too.

Answer 2

The question is to decide whether the set $X = \{100,10011,00110\}$ is a uniquely decodable variable-length code or simply a code, in the sense of [1]. This question can be solved by using the Sardinas–Patterson algorithm but in this special instance, a much simpler proof is possible. Indeed $X$ is a suffix code, that is, a set of words none of which is a suffix of any other. And any suffix code is a code.

[1] J. Berstel, D. Perrin, C. Reutenauer (2010). Codes and automata. Encyclopedia of Mathematics and its Applications 129. Cambridge: Cambridge University Press. ISBN 978-0-521-88831-8. Zbl 1187.94001