Äquivalenz zweier DEA's < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 12:16 Mo 20.07.2009 | | Autor: | RalU |
| Aufgabe | Hallo,
die beiden DEA's (siehe Bild) sollen auf Äquivalenz geprüft werden, d. h. es soll geprüft werden, ob beide die gleiche Sprache akzeptieren.
[Dateianhang nicht öffentlich] |
Das Vorgehen an sich ist mir ja klar.
1) Beide DEA's zu einem zusammenfassen.
2) Algorithmus zur Bestimmung der DEA-Unterscheidbarkeit ausführen. (Das wurde mit der Tabelle unter den DEA's ansatzweise durchgeführt) Das Prinzip des Algorithmus ist:
im ersten Schritt immer dann eine '1' in der Tabelle eintragen, wenn gilt: genau einer der beiden betrachteten Zustände ist akzeptierend. Im 2. Schritt müsste man, beispielsweise auch um einen Minimalautomaten zu bauen, die Tabelle nochmals durchgehen und überall da eine '2' eintragen, wo die gleiche Eingabe NICHT zu ein und demselben Zustand führt, eben zu unterscheidbaren Zuständen führt. Natürlich braucht man im 2. Schritt nur die Tabelle dort zu betrachten, wo noch keine '1' drin steht. Wenn man die Schritte 1 und 2 für die gesamte Tabelle ausgeführt hat, ist der Algorithmus beendet und man könnte einen Minimalautomaten bilden. Die leeren Tabellenfelder sind dann die äquivalenten Zustände.
Um zu prüfen, ob die beiden DEA's äquivalent sind, reicht es aus, die beiden Startzustände in der Tabelle zu prüfen.
Was ich nicht verstehe ist, warum die Tabelle bei den beiden Startzuständen (im Schnittpunkt A/C) leer bleibt (bezüglich 2. Schritt des Algorithmus).
Von A gehe ich doch mit 0 wieder in A. Von C gehe ich mit 0 in D. Und mit A und D hab ich doch schon mal 2 unterscheidbare Zustände. Jetzt prüfe ich noch von A mit 1 komme ich in B und von C mit 1 komme ich in E. Auch hier hab ich mit B und E 2 völlig andere Zustände. Deshalb müsste meiner Meinung nach dort eine '2' in die Tabelle und damit wären die Startzustände unterscheidbar und damit die beiden DEA's NICHT äquivalent.
Weiß jemand, wo mein Fehler liegt?
Gruß, Ralf
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Mi 22.07.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
