Automatenminimierung

Neue Frage »

Auf diesen Beitrag antworten »
Ceowl Automatenminimierung

Meine Frage:
Ich soll einen Minimalautomaten erstellen, hab nun alle Schritte des Table-Filling-Algorithmus abgearbeitet und bekomme ein Zustandspärchen zu viel raus, weswegen ich ihn in keinen neuen DEA konstruieren kann. Ich habe die gesamte Aufgabe in der angehängten Bilddatei zusammengefasst. Könnte mir jemand meinen Denkfehler erklären?
Vielen Dank schon mal.





Meine Ideen:
Siehe Anhang.
 
Auf diesen Beitrag antworten »
as_string

Ich versteh nicht, warum Du (1,2) noch drin hast. In der oberen Tabelle (mit dem ersten 0) landest Du doch schon auf (3,5), und (3,5) ist markiert, weil 3 final ist, 5 aber nicht, also ist (1,2) auch markiert (sprich nicht äquivalent).

Also hast Du nur noch die Paare (3,6) und (4,7), die unmarkiert sind. Man kann ja auch "sehen", dass die Äste ab 3 und ab 6 identisch sind: Solange das Wort zuerst nur aus Einsen besteht, bleibt es auf 3 bzw. 6 (also auf einem finalen Zustand), sobald die erste 0 kommt, geht es jeweils zur 4 bzw. 7, die beide keinen finalen Zustände sind. Egal, wie es dann im Wort weiter geht, bleibt es auf 4 bzw. 7, kann also nie wieder einen finalen Zustand erreichen.

Gruß
Marco

PS: Das ist lange her, ich bin mir nicht sicher, ob ich das noch alles richtig weiß...
Auf diesen Beitrag antworten »
Ceowl

Sorry für die späte Rückmeldung!

Also dass 1,2 falsch unmarkiert ist macht Sinn - das ist auch genau das Zustandspärchen welches dann beim Konstruieren Probleme machen würde. Ich verstehe nur nicht wie das Pärchen 3,5 (0-er Tabelle) zu der Markierung von 1,2 führt? Das Pärchen 3,5 liegt ja nicht innerhalb der Menge der möglichen Zustandspaare und sollte deswegen nicht zu einer Markierung führen... Wäre das Pärchen also 5,3 und nicht 3,5 wäre für mich alles schlüssig.
Auf diesen Beitrag antworten »
as_string

Nee, die Reihenfolge spielt doch keine Rolle. Wenn in einem Paar eines final ist, das andere nicht, wird es markiert.
Dass man die Tabelle quasi "halbiert" ist ja nur der Tatsache geschuldet, dass das Paar (p,q) äquivalent mit (q,p) ist.

Gruß
Marco
 
Auf diesen Beitrag antworten »
Ceowl

Na gut - das erklärt so einiges. großes Grinsen
Danke!
 
Neue Frage »
Antworten »


Verwandte Themen