Wann genau akzeptiert ein KA ein Wort?

Question

Hi, habe nochmal eine kurze Frage bzgl. der Kellerautomaten: Wann genau akzeptiert ein Wort? Klar, dass er im Endzustand sein muss, auch klar das keine weiteren Überführungen zur aktuellen Konfiguration möglich sein darf, aber wie sieht's mit dem Keller aus? Muss der leer sein (also auf k0) oder ist das egal, wenn da noch was drauf steht? Danke!

Answer 1

Der Keller muss nicht leer sein. Das Wort muss vollständig abgearbeitet sein und der Kellerautomat muss in einem Endzustand sein. Allerdings sind nach dem Einlesen des letzten Zeichens noch lambda-Übergänge möglich, was in verschiedenen Aufgaben ausgenutzt wird, um in einen Endzustand zu wechseln.

Tobias (Tutor)