Nächste Seite: Präfixeigenschaft Aufwärts: Deterministische kontextfreie Sprachen Vorherige Seite: Deterministische Kellerautomaten (DKAs)   Inhalt

Akzeptanzbedingungen

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äfix⁶¹ 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äfix⁶¹

Echtes Präfix bedeutet, daß das Wort der Gestalt ist, wobei das Präfix ist und

---