AU2-1b) Warum wird s4' Endzustand?

Question

Bei der Umformung in einen DEA, warum wird

1) s1' als Endzustand beibehalten? Ist das immer so?

2) s4' zum Endzustand? Über Eingabe der 0 kommt man zu {s0, s1, s2}, aber s4' enthält ja nur {s1, s2}

Answer 1

Hallo,

bei der Umformung eines nichtdeterministischen EA in einen deterministischen EA werden alle neuen Zustände $ s´_n$ zu einem Endzustand, wenn in der zugehörigen Zustandsmenge aus der Umformungstabelle auch ein Endzustand aus dem nichtdeterministischen EA enthalten ist.

Für die Fragen konkret bedeutet das:

1) Nein, es wird nicht immer automatisch $ s´_1$ zu einem Endzustand, sondern nur die Ersatzzustände, deren Zustandsmengen auch einen Endzustand aus dem nichtdeterministischen EA beinhalten. Dies ist hier der Fall, da $ \{s_1\} \equiv s´_1$ und $ s_1$ auch im nichtdeterministischen Automaten schon ein Endzustand war.

2) Analog zu oben gilt in der Lösung: $ \{s_1 , s_2\} \equiv s´_4$
Wie oben beinhaltet die Zustandsmenge den Zustand $ s_1$ aus dem nichtdet. EA und somit wird der Ersatzzustand auch im neuen det. EA ein Endzustand

Viele Grüße

Moritz (Tutor)