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

Schöne Ferien!
 

 

AU2-1b) Warum wird s4' Endzustand?

0 Punkte
49 Aufrufe
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}
Gefragt 7, Dez 2018 in Kapitel 2 von unfzt unfzt Lernwillige(r) (140 Punkte)  

Eine Antwort

0 Punkte
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)
Beantwortet 7, Dez 2018 von uvoaq uvoaq Lernwillige(r) (260 Punkte)  
...