Fano-Bedingung

Die Fano-Bedingung (nach Robert Fano) bezeichnet in der Kodierungstheorie der Informatik die Eigenschaft einer Sprache, präfix-frei zu sein. In einer Sprache, die der Fano-Bedingung genügt, gibt es also kein Wort, welches identisch mit dem Anfang eines anderen Wortes ist.

Präfix-freie Sprachen vereinfachen die Worterkennung, da nach jedem erkannten Wort sofort zum nächsten übergegangen werden kann. Eine weitere Vorausschau ist aufgrund der Präfixfreiheit nicht nötig.

Mit Hilfe der Shannon-Fano-Kodierung oder der Huffman-Kodierung lassen sich Kodierungen konstruieren, die die Fano-Bedingung erfüllen. Ein Code, der die Fano-Bedingung erfüllt, wird Präfixcode genannt.

Beispiele

• Die Sprache L = {0, 10, 110, 1110, 11110} (z. B. als Kodierung der Werte 0, 1, 2, 3, 4) ist präfixfrei und genügt damit der Fano-Bedingung.
• Die Telefonnummern eines Telefonbuchs eines Vorwahlbereichs genügen ebenfalls der Fano-Bedingung. Dies ist technisch notwendig, weil Telefonvermittlungsstellen (zumindest im Festnetz) gewählte Nummern Ziffer für Ziffer betrachten und sofort eine Verbindung herstellen, sobald eine vollständige Nummer gewählt wurde.
• Die deutsche Sprache hingegen genügt nicht der Fano-Bedingung, weil z. B. „bei“ ein Wort der deutschen Sprache ist und zugleich Präfix von „beide“ ist.
• Der Morsecode erfüllt die Fano-Bedingung, wenn die längere Pause zwischen zwei Zeichen als drittes Symbol der Sprache betrachtet wird. Eine Folge der beiden Symbole kurzes Signal und langes Signal würde die Fano-Bedingung nicht erfüllen.

Formale Definition

Sei ${\displaystyle \mathbf {\mathit {L}} }$ eine Sprache und ${\displaystyle \varepsilon }$ das leere Wort. ${\displaystyle \mathbf {\mathit {L}} }$ erfüllt die Fanobedingung, ist also präfixfrei genau dann, wenn ein Gefüge ${\displaystyle uv}$ von zwei Wörtern der Sprache nur dann ein Wort sein kann, wenn einer der Bestandteile das leere Wort ist:

${\displaystyle \forall u,v,w\in \mathbf {\mathit {L}}$ :(w=uv\implies u=\varepsilon \lor v=\varepsilon )}

Automat

Ein deterministischer Kellerautomat, der mit leerem Keller akzeptiert, akzeptiert genau die Sprachen, die die Fano-Bedingung erfüllen.

Literatur

• Rainer Malaka, Andreas Butz, Heinrich Hußmann: Medieninformatik: Eine Einführung. Pearson Studium, München 2009, ISBN 978-3-8273-7353-3, S. 74–77.