Die letzten 5 Beiträge |
Ceowl |
Na gut - das erklärt so einiges.
Danke! |
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 |
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. |
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ß... |
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.
Ceowl hat dieses Bild (verkleinerte Version) angehängt:
|
|
|