Ψ Die Informatikseite

Menü

Akzeptanzbedingungen deterministischer Kellerautomaten

Bei NKAs für kontextfreie Sprachen sind die Akzeptanzbedingungen durch leeren Keller oder Endzustand äquivalent. Bei DKAs ist dies nicht so. Leerer Keller ist schwächer als Endzustand.
Dies ist deshalb so, weil die Berechnung abbricht, wenn der Keller leer ist. Habe wir ein Wort, dessen echtes Präfix61 auch ein Wort der Sprache ist, so hält die Berechung nach dem Durchlauf des Präfixes verwerfend an, da der Keller leer ist, da ja das Präfix akzeptiert wird, kommt es alleine vor. Mit der Endzustandsakzeptanz könnten wir bis zum Ende laufen.

Fußnoten

... Präfix61
Echtes Präfix bedeutet, daß das Wort der Gestalt $xy$ ist, wobei $x$ das Präfix ist und $y\not=\epsilon$