Hallo,
ich suche einen Algorithmus, mit dem sich die Isomorphie zweier Endlicher Deterministischer Automaten (DEA) belegen oder widerlegen lässt.
Danke.
Ben
Was meinst Du mit Isomorphie ? Nur dass sie die geliche Sprache akzeptieren, oder, dass sie bis auf Permutation der Nummerierung der Zustaände tatsächlich gleich sind (wobei letzteres natuerlich ersteres impliziert ?
Um ersteres festzustellen wuerde ich zunächst gemäß dem Satz von Myhill-Nerode einen minimalen Automaten für beide suchen und dann
auf „echte“ Isomorphie testen.
Für den test auf isomorphie würde ich wie folgt induktiv vorgehen:
Wir wollen Schritt fuer Schritt Zustaände des DEA B den Zustaenden des DEA A zuordnen.
In jedem Schritt sei eine Menge M von bereits „zugeordneten“
Zustaenden gegeben und phi sei die auf diesen
bereits definierte partielle (bijektive) Zuordnungsabblidung.
Am Anfang enthaelt diese nur den Startzustand von B, der dem Startzustand von A zugeordnet ist. (Wir nehmen mal and, dass sich
in beiden Automaten alle Zuataende aus dem Startzustand erreichen lassen.)
In jedem Schritt nehmen wir uns einen Zustand aus dieser menge und gucken uns alle ausgehenden Uebergaenge an (danach markieren wir ihn als „bearbeitet“, so dass wir das fuer jeden Knoten nur einmal machen).
Sei unser Zustand also z. Zunächst sehen wir nach, dass alle aus
diesem Zustand herausfuehrenden Uebergaenge auch in A aus phi(z)
herausfuehren (d.h. die selben Zeichen eingegeben werden können).
sei O=(O_1…O_n) die menge der aus z erreichbaren Zustände
und P=(P_1…P_n) seien die aus phi(z) erreichbaren Zustaende, wobei gleich indizierte mit dem gleichen Buchtsaben erreicht werden.
Wenn O_i noch nicht in M ist, fuegen wir es hinzu und definieren
phi(O_i) als p_i. Wenn O_i schon in M ist, pruefen wir, dass
phi(O_i)=p_i. wenn das nicht der Fall ist, sind die Automaten nicht isomorph.
Wenn am Ende alle Zustände in M und alle Zustände bearbeitet sind, sollten die Automaten isomorph sein (ich denke dass kann
man per induktion über die Schritte des obigen Verfahrens zeigen).
Wenn die Teile Zustände haben, die nicht aus dem Startzustan erreichbar sind (unnütze Zustände), dann wird das ganze unangenehmer. Ich würde so spoantan versuchen, zunächst Komponenten zu identifizieren, dann aus jdeder A Komponente einen
Zustand nehmen, und mit diesen als Startzustand und jedem Knoten aus jeder B Komponente als anderem Statzustand obigen Algorithmius laufen lassen, bis klar its ob es mindestens einen Isomprohismus zwischen den Komonenten gibt. Dann würde ich
mit den A Komonenten als linker und den B Komonenten als rechter seite einen bipartiten Graphen erzeugen, in dem es genau dann eine Kante gibt, wenn es zwischen den zei Komponenten einen Isomorphismus gibt und dann ein perfektes Matching suchen.
Bei NEAS sollte das Graphenisomorphieproblem auf das Automatenisomorphieproblem reduzierbar und letzreres damit NP-hart sein.
MfG
Martin
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo,
erstmal vielen Dank für die ausführliche Antwort.
Mit Isomorphie meine ich die Strukturgleichheit.
Zwei DEAs sind ja äquivalent, wenn beide die gleiche
Sprache akzeptieren. Oder anders gesagt: Beide sind
äquivalent, wenn deren Minimalautomaten isomorph sind.
Und genau diese Isomorphie wollte ich maschienell
nachweisen können. (Die Minimierung (Myhill-Nerode) konnte
mein Programm schon.)
Ich habe den Isomorphienachweis gestern Abend programmiert
und es funktioniert. 
Danke
Ben