Binary Strings: How to determine if decomposition is ambiguous Let's say I have the following decomposition:  
$$\{100,10011,00110\}^*$$
How would I determine if the decomposition is ambiguous or unambiguous?
 A: 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.
A: 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
