erster Lamda-Übergang, um das leere Wort zu akzeptieren

Question

Wenn der Automat von Aufgabe b) ein Wort prüfen soll, könnte es dann nicht passieren, dass er in Zustand s0 ist und aufrund des Lamda-Übergangs nach S4 das erste Zeichen dieses Wortes ignoriert und in den Endzustand übergeht. Das Wort würde zwar nicht akzeptiert werden, da der Lesekopf nicht rechts vom Wort steht, aber was würde dann passieren?

Vielen Dank!

Answer 1

Hallo uedqa,

prinzipiell reicht es bei einem nichtdeterministischen Kellerautomaten nicht, sich nur eine mögliche Konfigurationsfolge anzuschauen, sondern sobald eine Konfigurationsfolge existiert, die nach Abarbeitung des Wortes zu einem Endzustand führt, wird das Wort akzeptiert (siehe VL Folie 3,12). Es ist also "kein Problem", dass es auch eine Konfigurationsfolge gibt, in der das Wort nicht akzeptiert würde, solange es eine andere "akzeptierende" Folge gibt.

Ich hoffe, das beantwortet die Frage...

Viele Grüße

Jonas (Tutor)