Theo. Inf. : Algorithmus Minimierung Automaten

Trainee

Date of registration: Apr 10th 2002

Sunday, August 25th 2002, 1:52pm

Hi,

könnte jemand das Verfahren aus der Vorlesung zur Minimierung von Automaten posten? Das Skript ist da nicht ganz so hilfreich wie ich es gerne hätte...es schweigt sich z.B. über die Benennung der neuen Zustände/Partitionen aus.

Ich habe bei der letzten Klausur scheinbar ein Verfahren benutzt mit dem der Korrektor nicht ganz so zufrieden war. Man darf halt nur das staatlich anerkannte und von Lipeck abgesegnete Verfahren nutzen

)

TIA

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Sunday, August 25th 2002, 2:35pm

Ich mache das mal am Beispiel der Aufgabe 8a aus der letzten Klausur:

Schritt 1:
Zuerst bilden wir die Startpartition, also zwei Zustandsmengen, von denen die eine alle Endzustände enthält, die andere die restlichen Zustände:

	Source code
1	{ s0, s2, s4 } { s1, s3, s5 }

Nun benennen wir die beiden Mengen. Wie ist völlig egal, ich mache das immer mit römischen Zahlen einfach von links nach rechts durch:

	Source code
1	I: { s0, s2, s4 } II: { s1, s3, s5 }

Jetzt untersuchen wir für jeden Zustand, unter welchen Eingaben er in welche Partition überführt. Ich schreibe das immer unter die Zustände. Somit ergibt sich:

	Source code
1 2 3	I: { s0, s2, s4 } II: { s1, s3, s5 } a->II a->II a->II a->II a->I a->II b->I b->I b->I b->II b->I b->II

Schritt 2:
Nun wird jede Zustandsmenge in neue Zustandsmengen aufgeteilt, abhängig von den Übergängen. Für die Menge I gibt es keine Aufteilung, da dort alle Übergänge identisch sind (a->II, b->I). II hingegen wird aufgeteilt. Damit ergibt sich folgende neue Aufteilung:

	Source code
1	{ s0, s2, s4 } { s3 } { s1, s5 }

Wir numerieren wieder durch:

	Source code
1	I: { s0, s2, s4 } II: { s3 } III: { s1, s5 }

... und untersuchen wieder die Übergänge:

	Source code
1 2 3	I: { s0, s2, s4 } II: { s3 } III: { s1, s5 } a->II a->III a->III a->I a->III a->III b->I b->I b->I b->I b->III b->III

Schritt 3:
Genau wie in Schritt 2 teilen wir wieder auf. Es ergibt sich dann:

	Source code
1	{ s0 } { s2, s4 } { s3 } { s1, s5 }

Nach der Numerierung und der Untersuchung der Übergänge ergibt sich:

	Source code
1 2 3	I: { s0 } II: { s2, s4 } III: { s3 } IV: { s1, s5 } a->III a->IV a->IV a->II a->IV a->IV b->II b->II b->II b->II b->IV b->IV

Wie man sieht ist keine weitere Aufteilung mehr möglich. Damit sind wir fertig. (Wäre allerdings noch eine Aufteilung möglich, müßten wir natürlich weitermachen ...)

Also fallen die Zustände s2 und s4 zu einem Zustand s2/4 zusammen sowie die Zustände s1 und s5 zu s1/5. s3 und s1/5 sind dabei Endzustände.

Eine Zustandsübergangstabelle mache ich jetzt mal nicht, das sollte nicht so schwer sein.

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962