Zeigen dass Minimalautomat minimal ist

[Mr.B]

Hey,
kann mir vllt einer erklaeren wie ich zeige dass ein Minimalautomat auch wirklich minimal ist?
Habe hier eine Formelsammlung von J. Flick die ich aus dem Forum habe, da macht er so eine Tabelle in der er die Zustaende auf ihr Akzeptanzverhalten ueberprueft....allerdings werde ich nicht wirklich schlau daraus.

Waere echt super wenn ihr mir so kurzfristig noch helfen koenntet, eine Erklaerung mit evtl. nem kleinen Beispiel waere super

Danke schonmal

[jls]

Wenn man einen Minimalautomaten erstellt nach dem iterativen Verfahren aus der Vorlesung, sollte meiner Meinung nach (bitte ggf korrigieren!) automatisch bewiesen sein, dass der Automat minimal ist, wenn nach weiteren Iterationen keine Veränderungen mehr auftreten (weil wir dann ganz einfach alle unterschiedlichen Äquivalenzklassen gefunden haben) - oder?

[noelma]

Hi Mr.B,

eine allgemeine Erklärung hat franzose hier ->http://www.fachschaft.informatik.tu-dar ... 56&t=20306 schon gegeben.
Als Beispiel nehmen wir jetzt mal den Automaten aus Übung 4 Aufgabe G2:
Als erstes unterteilst du die Zustände in akzeptierend (also Zustände 0, 1, 2, 4) und nicht akzeptierend (Zustände 3, 5).
Nun gehst du jeden Zustand durch und schaust, ob er bei einer Transition in einem akzeptierenden (als al abgekürzt) oder nicht akzeptierenden Zustand (als be abgekürzt) kommt.
- a | b
0 be al
1 al be
2 al be
4 al be
3 al al
5 al al

Da jetzt bei den al's der Zustand 0 aus dem Rahmen fällt (da er als Einziger in der Gruppe bei einem a in die be-Gruppe geht und bei einem b in seiner Gruppe bleibt) wird er aus der Gruppe der al's rausgenommen und bekommt seine eingene Gruppe (Äquivalenzklasse) (die ab jetzt als ga abgekürzt wird)
Jetzt wird das ganze wiederholt, bloß das wir ja jetzt drei und nicht mehr zwei Gruppen haben.
- a | b
1 ga be
2 al be
4 al be
3 al al
5 al al
0 be al

Nun fällt bei den al's der Zustand 1 aus dem Rahmen (da er als Einziger in der Gruppe bei einem a in die ga-Gruppe wechselt), wird wieder rausgenommen und bekommt wieder seine eigene Gruppe (Klasse).
Das ganze macht man dann solange, bis in den einzelnen Gruppen keiner mehr aus dem Rahmen fällt. Die einzelnen Gruppenmitglieder representieren dann im Minimalenautomaten zusammen einen einzigen Zustand.

Ich hoffe, ich konnte dir damit etwas helfen.

Gruß
Nora

[Mr.B]

Also danke erstmal .
Wie man den Minimalautomaten baut weiss ich, mir war nur nicht so recht klar dass der Algorithmus dafuer als Beweis aussreicht.
Trotzdem nochmal danke an dieser Stelle!

Gehe ich jetzt recht in der Annahme, dass in den Klausuren nur dabei steht dass man die Minimalitaet beweisen soll damit man nicht einfach den Minimalautomaten erraet und und damit seine Punkte bekommt...dass man also den Algorithmus anwenden muss auch wenn man schon weiss wie der Minimalautomat aussieht?

[igor.a]

Bezieht ihr das auf die WS 08 - Klausur, Aufgabe 2?

Dazu hätt ich eine Frage: lässt sich bei euch der determinisierte Automat minimieren?

[franzose]

@ Mr.B: so habe ich das auch verstanden. man muss auch wirklich zeigen, dass der Automat nur die Mindestanzahl an Äquivalenzklassen hat. Der Algorithmus aus der Vorlesung tut genau dies meiner Meinung nach.

@ igor.a: das kann man im Allgemeinen nicht sagen. Je nach dem wie dein NFA ist, hast du auch mehr oder weniger Zustände beim deterministischen Potenzmengen-Automat. Es hängt alsodavon ab, ob dein NFA bereits "möglichst effektiv" ist, dann hat der daraus entstandende DFA weniger äquivalente Zustände.....

[igor.a]

Der NFA war ja schon vorgegeben, d.h. man musste nur den üblichen Determinisierungsalgorithmus anwenden, der ein eindeutiges Ergebnis liefern dürfte.

[franzose]

ich denke ich weiß jetzt die Klausur die du meinst, wenn ich mich nicht irre, kann man den Zustand "0" und den Zustand "0,3" beim DFA zusammenfassen....