Minimierung eines DEA (Startpunkt "nicht erreichbar")

Question

Ich versuche gerade folgenden Automaten durch die Table-Filling-Methode zu minimieren.

Zuerst streicht man nicht zu erreichende Zustände: in diesem fall q1, allerdings ist der Startzustand auch nicht zu erreichen, wie geht man damit um? auch streichen und q3,q6 zu startzuständen machen?

Comments

Ich kenne kein explizietes Verfahren, aber vielleicht probierst du aus, den DEA in eine RegEx umzuwandeln und dann wieder in einen DEA.

Startzustand bleibt, q1 wird gestrichen.

Dann siehst du schon, dass du einige Zustände streichen kannst.

Answer 1

Der Startzustand wird am Anfang der Berechnung erreicht, noch bevor das erste Zeichen gelesen wird.

Wenn du {q₃,q₆} zum Startzustand machst, dann kannst du nicht unterscheiden, ob du bereits ein a oder ein b gelesen hast. Außerdem widerspricht "bereits ... gelesen hast" dem, was ein Startzustand leisten soll.