Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

Die Fano-Bedingung (nach Robert Fano) bezeichnet in der Codierungstheorie der Informatik die Eigenschaft einer Sprache, präfix-frei zu sein. In einer Sprache L, die der Fano-Bedingung genügt, gibt es kein Wort, das Präfix eines anderen Wortes ist.

Eine Präfix-freie Sprache könnte sein: {0, 10, 110, 1110, 11110}. Dies könnte eine Kodierung der Werte 0, 1, 2, 3 und 4 darstellen. Die deutsche Sprache hingegen genügt beispielsweise nicht der Fano-Bedingung, weil "bei" ein Wort ist und zugleich Präfix von "Beispiel", was auch ein Wort der Sprache ist.

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

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

Satz: Seieine Sprache. 
Parser-Fehler (<math_output_error>): \forall  u,v,w \in \mathbf{\mathit{L}},  (w = uv \implies v = \epsilon)