How to prove that a code has an unique decodability 
*

*I have the alphabet: $A=\{a,d,k,u\}$,  

*The code: $c=110011100111010$

*An code words: 
$$
\begin{array}{|c|c|c|c|}
\hline
x \in A& a & d & k & u \\ \hline
\gamma (x) & 001 & 110 & 11 & 10\\ \hline
\end{array}
$$
The Kraft's inequality is true: $(2^{-3})*2+(2^{-2})*2=\frac{3}{4} \le 1$
But it is not prefix code: (the code of $k$ is in the beginning of the code of $d$)

So how can I prove that there is an unique decoding for $c$? 

I found this solution but dont understand it: (can it be transferred into graphics?)
$\gamma$  seems to be bijective
$M_0=\{001,110,11,10\}$
$M_1=\{M_0^{-1}M_0 \cup M_0^{-1}M_0=\{0\} \cup \{0\} = \{0\}\}$
$M_2=\{M_1^{-1} M_0 \cup M_0^{-1}M_1=\{01\} \cup \{\emptyset\} = \{01\}\}$
$M_3=\{M_2^{-1} M_0 \cup M_0^{-1}M_2=\{\emptyset\} \cup \{\emptyset\} = \{\emptyset\}\}$
$[\Rightarrow] \ \forall \ n \geq 4 \ \wedge n \in \mathbb{N}^+ \ \ M_n=\emptyset$
$\Rightarrow M_1 \cap M_0 = \emptyset; \ M_2 \cap M_0 = \emptyset; \ \forall n \geq 3 \  M_n \cap M_0 = \emptyset$
$\Rightarrow \gamma $ is decodable
 A: If you're only interested in decoding bit strings of finite length, you can do it as follows.
Suppose we are given a bit string $D$ of finite length which comes from encoding a word $W$ over the alphabet $A$ according to the code in your question.
First, observe that any triple $001$ in $D$ must come from an $a.$ There's no other way to produce such a triple with your code. So we have located all the $a$s in $D$ and can split $D$ accordingly into pieces which are codes of words over the alphabet $\{d,k,u\}.$ Let's call such a (non-empty) piece $E.$ By looking at the codes of $d,k,u,$ we see that $E$ cannot contain two consecutive zeros, that it cannot start with $0,$ and that it must have an even number of $1$s (possibly none) at the end. Those $1$s at the end of $E$ must be the code of some word $k\cdots k$ (possibly empty). Let's discard those $1$s at the end of $E$ and call the remaining code $F.$ If $F$ is empty, we are done. If not, $F$ is of the form
$$
F = (1^{m_1}0) \ldots (1^{m_k}0)\qquad with\ exponents\ m_1,\ldots,m_k\geq 1.
$$
This follows from the properties of $E$ noted above. Each $0$ in $F$ must come from the end of the code word of either a $u$ or a $d.$ So we have located some boundaries of code words in $F,$ which means that in order to decode $F,$ we can decode each piece $1^{m_j}0$ separately. So let's consider such a piece $G = 1^m0$ with $m\geq1.$ By looking at the admissible code words, it's "very easy" to see that if $m$ is even, i.e. $m = 2r$ with $r\geq 1,$ then $G$ must be the code of $k^{r-1}d,$ and if $m$ is odd, i.e. $m = 2s+1$ with $s \geq 0,$ then $G$ must be the code of $k^su.$
All in all, we have uniquely decoded the given bit string $D.$
A: The solution that you included is using the Sardinas-Patterson algorithm for proving unique-decodability in a variable-length codeset.
Preface: I'm going to use the following vernacular:


*

*"codeset" refers to the whole mapping of source symbols to sequences of code symbols. For example: a -> 011, b -> 11, c -> 001, etc.

*"code" is just the sequence of code symbols corresponding to a single source symbol. For example: "011" (corresponding to "a")

*"code-string" is a string of code symbols produced by either a single code or concatenating multiple codes.


The basic intuition behind the theorem is that, if a codeset is not uniquely-decodable, then there exists a code-string which can decode to two different source strings, and that means that there exist (at least) two different source strings which encode to the same code-string. So, if you can find two source strings which yield the same code-string, you've proven non-unique-decodability.
Trying to brute-force search for matching encoded strings would only terminate in the non-uniquely-decodable case, and, even then, in NP time. Sardinas and Patterson realized that you only need to compare pairs of codes of unequal length wherein the shorter of the two (call it "A") one of the pair is the prefix of the other (call it "B"). Those are the only pairings which could yield an encoded string which begins the same way. After that, it's just a matter of resolving the "dangling suffix" left over from B after you remove A from it. If you can find another code that starts with this dangling suffix (or that the dangling suffix starts with), then you can add that to the shorter A code... yielding a new suffix to resolve. 
If you ever end up with a suffix with exactly matches one of your codes, then you've found two source strings which give the same coded string, and the codeset is not uniquely decodable. However, if you end up with a suffix which does not match the beginning of any of your codes, then that search terminates.
Using your codeset as an example...
$$
\begin{array}{|c|c|c|c|}
\hline
x \in A& a & d & k & u \\ \hline
\gamma (x) & 001 & 110 & 11 & 10\\ \hline
\end{array}
$$
There are only two source symbols which could give you the same start of a coded string: d and k:
$$
\begin{array}{|c|c|c|c|} \hline
source & matching & suffix \\ \hline
d & 11 & 0 \\ \hline
k & 11 \\ \hline
\end{array}
$$
This leaves a 0 at the end of d's code that we have to help k resolve. What's a source symbol we can append to k to deal with that 0? We can append a.
$$
\begin{array}{|c|c|c|c|} \hline
source & matching & suffix \\ \hline
d & 110  \\ \hline
ka & 110 & 01  \\ \hline
\end{array}
$$
So, a gave us a 0 to "catch up" to the coded string of d, but now ka has a suffix of 01 that needs to be matched by d. Do we have any code that starts with 01? No, so there's nothing we can do to make these two coded strings equal. Since "k" and "d" are the only two strings where one is a prefix of another, we've checked all possibilities, so the codeset is uniquely-decodable.
To describe the general algorithm, Sardinas and Patterson use the notation you see in the solution: $X^{-1}Y$ means "The set of all suffixes produced from removing an element in X from a longer element in Y". More formally, it's a set of suffixes, s, where code-string x exists in X and xs (x with the suffix) is in Y: $X^{-1}Y = \{ s \, | \, xs \in Y \, and \, x \in X \} $
With this notation, you start by finding all suffixes you codes can generate against each other, which is:
$$M_1 = M_0^{-1}M_0 = \{ 0 \}$$ 
Notice that this 0 is the same as the suffix which differentiated the encodings of "d" and "k". earlier. (The solution you posted does this twice and takes the union, which is redundant in the first iteration, BTW). Now we have a set of all of the possible leftovers or "dangling suffixes" possible from encoding two single source symbols where one's code is a prefix for the other. We now need to check to see if:


*

*Any of the suffixes in $M_1$ are prefixes of one of our codes in $M_0$ (the suffixes, therefrom, making up $M_1^{-1}M_0$), or

*Any of the codes in $M_0$ are prefixes of one of our suffixes in $M_1$ (the suffixes, therefrom, making up $M_0^{-1}M_1$).


If we union these two sets,
$$M_2 = M_1^{-1}M_0 \cup M_0^{-1}M_1 = \{ 01 \}$$
Notice that this 01 is the same as the suffix which differentiated the encodings of "d" and "ka". earlier. We now have the set of all possible suffixes from the encoding of a source string of length 1 and a source string of length 2 where one of the encodings is a prefix for the other (just like the last step, but with a single source symbol added to one of our candidate source strings).
Doing this one more time, we see if any of these suffixes are prefixes of one of our codes or if one of our codes is a prefix for one of the suffixes:
$$M_3 = M_2^{-1}M_0 \cup M_0^{-1}M_2 = \{ \emptyset \}$$
Which means that there are no elements in $M_2$ which serve as a prefix for one of our codes, and none of our codes can "consume" part of any suffix in $M_2$, so there's no way to generate two identical code strings from two different source strings, and our codeset is uniquely-decodable.
Now, I should point out, here, that the algorithm specifies three stopping conditions:


*

*If any element in a set of suffixes $M_i$ exactly matches any of our codes, then the codeset is not uniquely-decodable because we can resolve that suffix with the addition of one more source symbol to one of our source strings, leaving no suffix, thereafter. This is what your "intersection" check at the end of the solution was doing. It was checking to see if there were any common elements between the original code-set and any of the sets of suffixes.

*If the set of generated suffixes $M_i$ at any iteration is empty, then the codeset is uniquely-decodable because none of the elements in the last set are prefixes of any of our codes, and vice-versa, so there's no way of resolving any of the dangling suffixes.

*Lastly, if the generated set of suffixes $M_i$ exactly matches an earlier set $M_k$, then the codeset is uniquely-decodable because we have, essentially, looped back to the same set of suffixes, which will keep failing to completely resolve via case #1.

