Anmerkung Nichtdeterminismus

Question

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!

Answer 1

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)