Automatenminimierung

Benutzeravatar
_andreas
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 13. Okt 2009 13:45
Kontaktdaten:

Automatenminimierung

Beitrag von _andreas » 31. Aug 2011 22:07

Hi

Egal was ich mir bis jetzt dazu durchgelesen habe, ich komm einfach nicht dahinter.
Automatenminimierung eines DFAs (einen NFA kann man ja scheinbar nicht effektiv minimieren wie ich verstanden habe) umfasst die Eliminierung derjenigen Zustände, die vom Startzustand nicht erreichbar sind. Logisch. Doch wie beweisen? ist "man sieht doch dass da kein Pfad von A nach B führt" mathematisch genug?

Dann müssen diejenigen Zustände zusammengefasst werden, die äquivalent sind. Hmm, hier haperts schon. Ich finde unzählige Anleitungen mit Tabellen, die jeder für sich selbst neu zu erfinden scheint.
In einem Beispiel werden Zahlen eingetragen, im anderen Buchstaben oder Eingabewerte-Abfolgen oder "Nicht-Äquivalente Folgezustände", jedenfalls blicke ich da einfach den Sinn nicht oder kann zumindest aus den durchgehend knapp formulierten "Erklärungen" nichts verständliches ziehen. Im Script verstehe ich auch nur bahnhof, da ich mir das bisher nicht mal bildlich vorstellen kann, was man da wirklich aktiv treibt, wenn man die Äquivalenz zweier Zustände erklärt.

Dann sehe ich oft den Algorithmus dazu, der in etwa so aussieht:

Code: Alles auswählen

begin
for p ∈ F ∧ q ∈ (Q − F ) do markiere (p,q)
for jedes Paar von verschiedenen Zuständen (p,q) in FxF oder (Q-
F)x(Q-F) do
if für ein Eingabesymbol a ist (δ ( p , a ), δ (q, a)) markiert then
begin
Markieren von (p,q);
Rekursives Markieren aller nicht markierten Paare auf der
Liste für (p,q) und auf den Listen der anderen Paare, die
bei diesem Schritt markiert werden
end
else /* es ist kein Paar (δ ( p, a), δ (q, a)) markiert */
for alle Eingabesymbole a do
(p,q) ist auf die Liste für (δ ( p , a ), δ (q, a)) zu setzen, falls nicht
δ ( p , a ) = δ ( q, a ) gilt
end
(kopiert mit schlechter Formatierung aus [link] Folie #8, da foren keine tabs mögen)

Es wird von "Markierung" gesprochen. Doch was soll ich womit markieren? Einen Buntstift nehmen und anmalen? Einen Matrix-Wert hochzählen? Kreuzchen setzen?
Vermutlich soll ich eine Tabelle aufsetzen, wo ich für jede mögliche Zustandspaarung eine mögliche Äquivalente Eigenschaft festhalten soll. Doch was genau gehört hier rein? Wenn ich zwei gleiche/äquiv. Zustände markieren soll, was ist dann mit Folgezuständen gemeint?

Auf dieser Seite fand ich eine anschauliche Tabelle, die aber leider im einzigen Beispiel ein solches wählt, wo die Nicht-Akzeptierenden Zustände keine Verbindung untereinander haben. Hmmm.

Die Zahlen-Tabelle fand ich auf dieser Seite und zwar im PDF auf Folie Nr. 33/34. Ist mir zwar einleuchtend wenn ich so draufschaue, etwas am Automaten rumrate und probiere, wie die Zahlenwerte zusammenkommen weiß ich aber nicht so genau. Wäre einer so nett es mir zu erklären? Warum bleibt q0 und q1 leer (sind ja offenstl. äquiv.), q0 und q2 dahingegen aber =1 ?? Sie haben beide 2 Relationen ausgehend von sich, 0 und 1. Müssten sie nicht auch äquivalent sein?

Bitte helft mir!

kain
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Re: Automatenminimierung

Beitrag von kain » 31. Aug 2011 23:14

Also, ich kenne zwei Arten (die eigl. das gleiche sind), die eine mit den Kreuzen und die andere mit den Aufteilung in Klassen.

Nehmen wir die mit den Klassen:

(Nichterreichbare Zustände vorher oder nachher "eleminieren", ist egal, hauptsache dein minimaler Automat hat keine nichterreichbaren Zustände)

1.) schreibe alle Zustände nebeneinander auf und teile sie in akzeptierende und nichtakzeptierende auf
z.B.: 0 1 2 3 | 4 5
alpha | beta
alpha = akz., beta = nichtakz.

das ist jetzt ~0

2.) erstelle Tabelle, mit drei Spalten: delta 1, a, b
spalte delta kommen alle Zustände und in die Spalten a und b, kommen jetzt die Klassenbez. alpha bzw. beta. Je nachdem welches es ist. Das heißt, man schaut jetzt zu welcher Klasse man kommt mit a oder b. Also wohin kommt man mit a oder b, angenommen man würde zu 4 kommen, dann schreibt man in die Tabelle beta rein.

3.) Schritt 2.) bis die Tabelle fertig ist. Jetzt schaut man sich die Zustände 0 1 2 3 (alpha) und 4 5 (beta) genauer an.
Die Tabelle sieht ungefähr so aus (nur Bsp.):

delta_0...a.....b
0.....alpha.....beta
1.....alpha.....beta
2.....alpha.....beta
3.....beta.....beta
4.....beta.....alpha
5.....beta.....alpha

Jetzt kann man erkennen, dass Zustand 3 "anders" ist, als die anderen "alphas".
Weiter mit Schritt 1.)

Also: ~1
0 1 2 | 3 | 4 5
alpha|beta|gamma

(die Bez. sind egal, es geht darum, dass die jeweiligen Zustände in den richtigen "Äquivalenzklassen" liegen)

Aus ~1 macht man die Tabelle delta 1, schreibt alles auf und schaut ob sich 0 1 2 und 4 5 in andere Klassen zerfallen.
Daraus resultiert dann ~2, => Tabelle delta 2... usw. bis eben ~2 = ~3 (bzw. bis es keine neuen Klassen gibt).

Jetzt schaut man, wie viele Zustände in einer Klasse liegen.
Angenommen:
0 1|2|3|4 5 => 0 und 1 kann man als einen Zustand zusammenfassen und 4 und 5 als einen anderen.


Ist alles evtl. unübersichtlich geworden, aber ich hoffe, ich konnte helfen. Egal ob diese Methode oder die mit den Kreuzen, es geht immer darum, die Zustände in verschiedene Äquivalenzklassen zu teilen, bis es nicht mehr geht. Zuständen in der selben Klasse werden zusammengefasst.

Benutzeravatar
_andreas
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 13. Okt 2009 13:45
Kontaktdaten:

Re: Automatenminimierung

Beitrag von _andreas » 1. Sep 2011 17:43

Wahnsinn, ich habs tatsächlich geblickt! Die Methode hilft enorm!

Gut dass ich nochmal nachgefragt habe :D

Antworten

Zurück zu „Archiv“