Vergleich zweier endlicher Automaten
-
Hallo zusammen,
wie kann man zumindest teilweise überprüfen, ob zwei Automaten in der Lage sind, die gleichen Alphabete zu verarbeiten?
Welche mathematischen Voraussetzungen müssen gelten?
Hat einer von Euch hilfreiche Quellen hierzu?
Danke!
-
Das Äquivalenzproblem ist bei endlichen Automaten entscheidbar, indem Minimalautomaten erstellt und dann verglichen werden.
Beispielsweise:
http://de.wikipedia.org/wiki/Deterministischer_endlicher_Automat#MinimierungWenn die minimalen Automaten gleich sind, dann sind die Automaten äquivalent.
-
curry-king schrieb:
wie kann man zumindest teilweise überprüfen, ob zwei Automaten in der Lage sind, die gleichen Alphabete zu verarbeiten?
indem man sich die Beschriftungen der Übergänge ansieht. Oder willst du die die Sprachen vergleichen?
-
Danke R.....!
Noch eine Frage.
Angenommen ich habe eine Eingabesequenz w einer kontextfreien Grammatik.
Außerdem liegt ein DFA vor.Wie kann ich effizient überprüfen, ob w ELEMENT L(DFA) ist?
Brutforce-mäßig ist mir die Lösung des Wortproblems klar.
Kennt Ihr aber neue Ansätze bzw. Stichwörter in diese Richtung etc....
Danke!
-
Wieso Brutforce? Man nehme w und fuettere seinen DFA damit. Landet man in einem akzeptierenden Zustand, so liegt w in L(DFA).
-
Sorry, das meinte ich mit Brutforce.
Ich suche nach besseren/effizienteren Ansätzen um zu testen, ob w auf dem DFA "läuft".
-
Eine untere Schranke fuer die Laufzeikomplexitaet ist O(n), wobei n die Laenge des Wortes w ist (n = |w|). Das Wort muss eingelesen werden, daran fuehrt kein Weg vorbei. Das Testen des Wortes durch den DFA benoetigt auch O(n) Schritte. Die Gesamtlaufzeit ist demnach O(n) + O(n) = O(n). Auch wenn du das Ueberpruefen durch den DFA beschleunigen kannst, beispielsweise zu O(lg n), bleibt O(n) + O(lg n) = O(n).