imported>Standspurtänzer: /* Beispiele */ Telefonnummern: Eigenschaft der Vermittlungsstelle, nicht des Telefons (Endgerät).

2025-11-11T22:27:14Z

Beispiele: Telefonnummern: Eigenschaft der Vermittlungsstelle, nicht des Telefons (Endgerät).

Neue Seite

Die '''Fano-Bedingung''' (nach [[Robert Fano]]) bezeichnet in der [[Kodierungstheorie]] der [[Informatik]] die Eigenschaft einer Sprache, [[Präfix (Theoretische Informatik)|präfix]]-frei zu sein. In einer Sprache, die der Fano-Bedingung genügt, gibt es also kein [[Wort (Theoretische Informatik)|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 [[Formale Sprache|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 [[Telefonnummer]]n 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#Bedeutung der kurzen und langen Pausen|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 <math>\mathbf{\mathit{L}}</math> eine [[Formale Sprache|Sprache]] und <math>\varepsilon</math> das [[Leeres Wort|leere Wort]]. <math>\mathbf{\mathit{L}}</math> erfüllt die Fanobedingung, ist also präfixfrei genau dann, wenn ein Gefüge <math> uv</math> von zwei Wörtern der Sprache nur dann ein Wort sein kann, wenn einer der Bestandteile das leere Wort ist:
:<math>\forall u,v,w \in \mathbf{\mathit{L}}: (w = uv \implies u = \varepsilon \lor v = \varepsilon)</math>

== 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.

[[Kategorie:Kodierungstheorie]]

Fano-Bedingung - Versionsgeschichte

imported>Standspurtänzer: /* Beispiele */ Telefonnummern: Eigenschaft der Vermittlungsstelle, nicht des Telefons (Endgerät).