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
ist, wobei 
das Präfix ist und
