Kompression I

Ein namhaftes IT-Unternehmen mit einem weitbekannten Logo wirbt für sein Betriebssystem damit, dass es ein Kompressionsverfahren hat, womit es alle Dateien auf höchstens die Hälfte der Länge komprimieren kann.

Formalisieren die Aussage des Unternehmens. Was hältst du von der Behauptung?

Hinweis: Ein Bitstring ist eine (endliche) Folge von $0$en und $1$en. Die Menge aller Strings über einer (endlichen) Menge $A$ (dem Alphabet) schreiben wir als $A^*$; Bitstrings schreiben wir also als $\{0,1\}^*$. Die Länge eines Strings $s$ schreiben wir als $|s|$.