0 Daumen
2,8k Aufrufe


Hallo, wir sollen zunächst einen gegebenen DFA in einen Minimalautomat umwandeln.

DFA M über dem Alphabet {0,1} und den Zuständen zo bis z5 wobei z5 der Endzustand ist.

Die Überführungsfunktion lautet so:

        z0     z1    z2    z3    z4    z5

o     z2     z3     z2    z3   z5     z5

1     z1     z1    z4     z4   z0     z5

Ich habe bereits die Tabelle gemacht und die Zustände (hoffentlich richtig) verschmolzen:

z0 und z3 zu z03

z0 und z2 zu z02

z1 und z3 zu z13

z1 und z2 zu z12

z0 und z1 zu z01

Danach habe ich diese Zustände zum Zustand z0123 zusammengeführt. Mein Problem ist,  ich weiß nicht, ob ich das bislang richtig gemacht habe... :( Und wie sieht dann der Minimalautomat aus?


Zum Schluss sollen wir noch zu vier gegebenen Äquivalenzklassen, bezüglich der Myhill-Nerode-Äquivalenzrelation jeweils zwei weitere Worte aus diesen Klassen angeben:

[Lambda] = {Lambda,                        ,                  ,....  }

[0] = {0,              ,                      ,....}

[01] = {01,           ,                ,....}

[010] = {010,              ,               ,....}


Vielen Dank im Voraus!

Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

*Hallo*

Male Dir den Automaten am besten mal auf. Damit ist die Minimierung wesentlich leichter.

Verwende dann diesen Algorithmus:


(Ab Minute 6:50)

Ich hoffe das hilft dir

gg

Avatar von

Vielen Dank,

hat mir sehr geholfen! : )

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community