Wieso ist der KA ndet?

Question

Ist der KEL-AF nichtdeterministisch weil er die Möglichkeiten 

(s0,a,k0)->(s2,k0)

(s0,b,k0)->(s1,k0)

besitzt? oder ist obiges deterministisch?

Warum ist der KA nichtdeterministisch? sieht für mich alles deterministisch aus...

 

Answer 1

Die von dir oben genannten Übergänge sind deterministisch.

Ich denke auch, dass der in der Musterlösung angegebene Kellerautomat deterministisch ist. Ich gebe dir recht, Aufgabenstellung und Lösung passen hier nicht 100-prozentig zusammen.

Allerdings gilt, dass jeder determistische Kellerautomat auch ein nichtdeterministischer Kellerautomat ist, nur eben eine besondere Form davon (Sprachmächtigkeit det. KA ist echte Teilmenge der Sprachmächtigkeit nichtdet. KA)

Melanie (Tutorin)