Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Automatenminimierung » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Automatenminimierung
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Ceowl
Grünschnabel


Dabei seit: 17.12.2020
Beiträge: 3

Automatenminimierung Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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:
Aufgabe 1.png

17.12.2020 20:08 Ceowl ist offline E-Mail an Ceowl senden Beiträge von Ceowl suchen Nehmen Sie Ceowl in Ihre Freundesliste auf
as_string as_string ist männlich
Haudegen


Dabei seit: 06.11.2013
Beiträge: 618
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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ß...
18.12.2020 01:40 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Ceowl
Grünschnabel


Dabei seit: 17.12.2020
Beiträge: 3

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Ceowl: 20.12.2020 19:39.

20.12.2020 19:14 Ceowl ist offline E-Mail an Ceowl senden Beiträge von Ceowl suchen Nehmen Sie Ceowl in Ihre Freundesliste auf
as_string as_string ist männlich
Haudegen


Dabei seit: 06.11.2013
Beiträge: 618
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
21.12.2020 01:30 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Ceowl
Grünschnabel


Dabei seit: 17.12.2020
Beiträge: 3

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Na gut - das erklärt so einiges. großes Grinsen
Danke!
23.12.2020 01:02 Ceowl ist offline E-Mail an Ceowl senden Beiträge von Ceowl suchen Nehmen Sie Ceowl in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Automatenminimierung