Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

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

+1 Punkt
64 Aufrufe
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!
Gefragt 30, Jan 2016 in HU-2-3 von uedqa uedqa Eins-Komma-Null-Anwärter(in) (1,550 Punkte)  
Bearbeitet 30, Jan 2016 von uedqa uedqa

Eine Antwort

0 Punkte
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)
Beantwortet 30, Jan 2016 von ufdzo ufdzo Tutor(in) (102,580 Punkte)  
...