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.)

Lambda Übergänge

0 Punkte
319 Aufrufe
Mir ist nicht klar, was die beiden Übergänge nach s0 mit der Beschriftung "lambda" bedeuten.

Ich verstehe das nun so, dass immer zuerst ein Lamba eingelesen werden müsste, damit der Automat überhaupt einen Endzustand erreichen kann. Aber kann Lambda nicht nur dann eingelesen werden, wenn das Wort leer ist? Oder kann man Lambda vor jedes Wort "schreiben" um den Anfang darzustellen?
Gefragt 4, Feb 2017 in 2016-N-03 von ukeze ukeze Lernwillige(r) (320 Punkte)  

2 Antworten

+1 Punkt
 
Beste Antwort

"lambda" bedeutet lediglich, dass der ndet. KA sofort in diesen Zustand wechseln kann ohne eine Eingabe zu lesen. Damit wird dieses "entweder - oder" in der Aufgabenstellung eingebunden. Entweder dein Wort ist Teil der oberen oder unteren Schleife des Zustandüberführungsdiagrammes (Schaubild).  

Dies ist auch zulässig, da wir einen nichtdeterministischen Kellerautomaten definieren. 

Hoffe ich konnte weiterhelfen :)

Beantwortet 4, Feb 2017 von uydht uydht Eins-Komma-Null-Anwärter(in) (2,270 Punkte)  
ausgewählt 4, Feb 2017 von ukeze ukeze
Ja, danke! :)
+1 Punkt
Wenn du dir die Sprache genauer anschaust handelt es sich eigentlich um zwei eigenständige Sprachen: entweder steht hinter jeder 1 ein $ oder hinter jeder 0.

Beim lesen von Wörtern in einem Kellerautomat hat man immer die Möglichkeit ein lambda zu lesen, also auch bevor man mit dem eigentlichen Wort anfängt (und zwischen jedem Zeichen beliebig oft). Somit hat man durch den lambda-Übergang die Möglichkeit sich für eine der beiden Sprachen zu entscheiden. Da in der Aufgabe nach einem nochtdeterministischen KA gefragt war, muss es nur eine Möglichkeit geben in einem Endzustand zu landen. Der n-det. KA rät somit am Anfang welche Sprache er wählt.
Beantwortet 4, Feb 2017 von ufdrm ufdrm Tutor(in) (102,020 Punkte)  
...