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

Anmerkung Nichtdeterminismus

+1 Punkt
81 Aufrufe

Hallo, ich habe eine  Verständnisfrage, die sich auf die Anmerkung zum Nichtdeterminismus des Kellerautomaten bezieht:

Könnte man die erste Zeile des Kellerautomaten (s0, lamda, k0 ) --> (se, k0) nicht auch einfach weglassen, dafür dann s0 ebenfalls als Endzustand definieren und somit verhindern, dass der Kellerautomat bereits schon in der ersten Zeile nichtdeterministisch wird?

Wenn man das nicht dürfte, wäre es schön, wenn jemand kurz erklären könnte, warum man das nicht darf :)

Vielen Dank!

Gefragt 9, Feb 2016 in KEL-AD von uudtm uudtm Lernwillige(r) (360 Punkte)  

Eine Antwort

0 Punkte
Hallo uudtm!

Ja, durch das Weglassen der ersten Übergangsregel und stattdessen der Definition von s_0 als Endzustand würde sich an der Funktionsweise des Kellerautomaten tatsächlich nichts ändern, das wäre also zulässig.

Nichtsdestotrotz bleibt dein Kellerautomat insgesamt nicht-deterministisch (was ja auch im Aufgabentext explizit so gefordert wird) wegen dem in der Anmerkung erwähnten doppelten Übergang von (s_1,a,a) und den Übergängen (s_2,lambda, k_0) gekoppelt mit (s_2, c, k_0).

Ich hoffe, das beantwortet deine Frage!

Viele Grüße,
Janine (Tutorin)
Beantwortet 9, Feb 2016 von uedqi uedqi Tutor(in) (108,510 Punkte)  
...