Beweis der Injektiität einer Codierung

Question

Aufgabe:

Man hat die Codierung
0 -> 00
1 -> 01
$ -> 1

Problem/Ansatz:
Wie beweise ich die Injektivität dieser Codierung?
f(x1)=f(x2) kann ich ja schwer nutzen, da ich ja Variablen schlecht codieren kann

Answer 1

Sei w ein Wort über dem Alphabet {0, 1}.

Dann gibt es ein w', so das

        w = 00w'

oder

        w = 01w'

oder

        w = 1w'

ist. w' ist eindeutig durch die Anzahl der führenden Nullen von w bestimmt. w kann also eindeutig dekodiert werden, falls w' eindeutig dekodiert werden kann.

Es ist |w'| < |w|. Nach endlich vielen Dekodierungsschritten kommt man entweder zu

        w' = 00

oder

        w' = 01

oder

        w' = 11

oder

        w' = 10.

In den ersten drei Fällen ist die Dekodierung eindeutig. Im letzten gibt es keine Dekodierung.