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,

Die Zustände s1,s2 und s3 kommen bei diesem Automaten nie alleine vor. Egal welche Eingabe man macht, man erreicht immer entweder mindestens zwei Zustände oder keinen. Zum Beispiel wenn wir 0 eingeben erreichen wir zwar s1 aber gleichzeitig auch s0. Somit kommen diese drei Zustände nie einzeln vor, weshalb wir sie auch nicht einzeln betrachten müssen.

Beim Algorithmus zum Umwandeln eines nichtdeterministischen in einen deterministischen Automaten trägt man nur die Zustände in der linken Spalte ab, welche in den anderen beiden Spalten bereits vorkamen.

Ich hoffe, das beantwortet deine Frage.

Viele Grüße,

Julia