Kriterium für einen Minimalautomaten
-
Hallo zusammen,
ich habe einen Automanten gegeben und soll zeigen, dass er minimal ist. Darunter steht als Hinweis, das der Automat genau dann minimal ist, wenn für alle x,y x \not{\sim} y gilt.
Ich vermute, dass damit gemeint ist, dass jeder Zustand seine eigene Äquivalenzrelation besitzt. Kann ich also folgende Regel formulieren:
Sei A ein Automat mit n Zuständen. Falls dieser genau n Äquivalenzrelationen bestitzt, dann ist er minimal.
Ist das richtig?
Danke
-
Nein es gibt natürlich nur eine Äquivalenzrelation. Es macht keinen Sinn zu sagen, dass der Automan n Relationen hat.
Ihr habt doch sicher das Verfahren zum minimieren von Endlichen Automaten behandelt. Wenn Du dieses Verfahren auf den gegebenen Automaten anwendest und er hinterher keinen Zustand weniger hat, war er bereits minimal.
Siehe auch hier unter Minimierung: http://de.wikipedia.org/wiki/Deterministischer_endlicher_Automat
-
Hi!
Vielleicht habe ich mich schlecht ausgedrückt, aber in Wikipedia steht folgendes:
"Da die Zustände des Minimalautomaten den Äquivalenzklassen der vom endlichen Automaten M akzeptierten Sprache unter der Nerode-Relation entsprechen, spricht man auch vom Äquivalenzklassenautomat:"
Falls nun diese Anzahl der Äquivalenzklassen gleich der Zustandsanzahl ist, muss es sich doch um den Minimalautomaten handeln. Darin steckt doch indirekt die Nerode-Relation.
Ja, das Verfahren der Minimierung kenne ich, aber wir sollen ausschließlich über die Äquivalenzklassen zeigen, dass der Automat minimal ist.
Danke
-
freakC++ schrieb:
Falls nun diese Anzahl der Äquivalenzklassen gleich der Zustandsanzahl ist, muss es sich doch um den Minimalautomaten handeln.
Ja, aber du hast oben "Anzahl der Äquivalenzrelationen" geschrieben.