Zusammensetzung des DEA nicht verständlich

Question

Ich verstehe nicht warum bis auf s0 keine Einzelzustände (also: s1, s2 und s3) betrachtet werden. Dies war doch das normale Vorgehen des Algorithmus in den Aufgaben zuvor.

So komme ich auf 7 anstatt der 4 Zustände.

Answer 1

Hallo,

wenn wir einen nichtdeterministischen Automaten deterministisch machen wollen, beginnen wir immer mit unserem Startzustand, der in der Regel s0 ist.
Danach arbeiten wir aber nicht die anderen Zustände des NEA ab. In unserer Übergangstabelle steht, welche Zustandsmengen erreicht werden, wenn wir im Zustand s0 eine Eingabe von 0 bzw. 1 erhalten ({s0,s1} bzw. {s0}). Nun nehmen wir alle Zustandsmengen in die linke Seite der Tabelle auf, hier also nur {s0,s1}, da wir für s0 ja bereits im ersten Schritt die Zustandsübergänge bestimmt haben, und gehen analog zu s0 vor. Dies tun wir, damit für jede Zustandsmenge in unserer Tabelle (die jeweils einen Zustand in unserem DEA darstellt) für jede Eingabe der Folgezustand (hier noch eine Menge von Folgezuständen) definiert ist. Da jede so erhaltene Zustandsmenge zu genau einem Zustand unseres DEA wird, hat somit jeder Zustand für jede Eingabe genau einen Folgezustand (siehe Definition DEA).

 

Ich hoffe, ich konnte dir weiterhelfen.

Liebe Grüße

Laura (Tutor)