Äquivalenzproblem
Neue Frage »

06.10.2004, 21:29 schokoladenzeit Auf diesen Beitrag antworten »
Äquivalenzproblem
Ist das Äquivalenzproblem für NEAs (d.h. die Frage, ob zwei beliebig gegebene NEAs diesselbe Sprache akzeptieren) entscheidbar? Wenn ja, geben Sie den Algorithmus an, falls nein, Begründung angeben.
06.10.2004, 21:56 WebFritzi Auf diesen Beitrag antworten »

Klar ist das entscheidbar. Hier mein Algorithmus:

code: 
1:
2:
3:
4:
5:
6:

NEA nea1 = TakeNEA(arbitrary);
NEA nea2 = TakeNEA(arbitrary);

return( nea1.Accept( nea2.Language() ) && nea2.Accept( nea1.Language() ) );
06.10.2004, 22:30 slyck Auf diesen Beitrag antworten »

Na so einfach ist das nicht. Ansonsten könnte man ja einfach auf nea1.Language().equals(nea2.Language()) machen ... da müßtest du schon angeben, wie z.B. Language() arbeitet. Gibt das die ganze Sprache zurück? Wie kommt accept() mit einer ganzen Sprache (= unendlich viele Wörter) klar? Wenn accept() false zurück gibt, heißt das bei einem NEA noch lange nicht, daß die Sprachen ungleich sind.

Das Problem sollte entscheidbar sein, aber eine Idee für den Algo habe ich gerade auch nicht ... vielleicht erstmal auf DEAs zurückführen?
06.10.2004, 22:52 WebFritzi Auf diesen Beitrag antworten »

Natürlich ist das so einfach!!! Ach ähm, was sind NEAs? Tanzen
07.10.2004, 09:27 slyck Auf diesen Beitrag antworten »

Nichtdeterministische Endliche Automaten ?!?
07.10.2004, 12:42 Mazze Auf diesen Beitrag antworten »

Also erstmal ein Paar Dinge. Ein endlicher Automat akzeptiert erstmal nur reguläre Sprachen. Das wesen des akzeptierens ist es, terminierend "ja" zu sagen oder aber terminierend "nein" zu sagen oder aber niemals zu terminieren. Ich kann zwar spontan keinen endlichen Automaten vorstellen der auf einer Eingabe nicht stoppt, aber da wir vom akzeptieren ausgehen, muss der Fall betrachtet werden.

Nun das Entscheidungsproblem.

Ein Entscheider muss terminieren! Da haben wir schon das erste Problem. Terminiert der Automat auf einer Eingabe nicht so kann nicht entschieden werden ob die Sprache überhaupt erkannt wird. Denn es handelt sich um 2 bel. NEA's. Es kann ja sein das der erste linearen Aufwand hat und der zweite exponentiellen. Der Zweite würde vielleicht sogar nach 20000 Mio Schritten zum Ziel kommen, allerdings müsste man solange warten bevor man entscheiden kann. Wenn man sicher stellt das die Automaten auf jeder Eingabe terminieren ist das Problem entscheidbar, terminieren sie nicht zwingend ist es nicht entscheidbar.
 Anzeige 
 
10.10.2004, 13:01 slyck Auf diesen Beitrag antworten »

Ein endlicher Automat terminiert immer (bei endlicher Eingabe). Wie soll es auch anders sein, da er die Eingabe genau einmal lesen muß (und danach ist er halt in irgendeinem Zustand, und fertig).

Der Unterschied zwischen NEA und DEA ist aber der: ein DEA (deterministischer endlicher Automat) gibt bei einer Eingabe ja (das Wort wird akzeptiert) oder nein (das Wort wird nicht akzeptiert) zurück. Ein NEA dagegen sagt ja (das Wort wird akzeptiert) oder nein (auf dem Weg, den ich gegangen bin, wurde das Wort nicht akzeptiert). Ein Wort wird aber von einem NEA akzeptiert, wenn es min. _eine_ akzeptierende Berechnung gibt. Ein nein vom NEA heißt also nicht, daß das Wort nicht in der Sprache des NEAs ist, sondern nur, daß er bei diesem Durchlauf keine akzeptierende Berechnung hingekriegt hat.

Da man jeden NEA in einen DEA umbauen kann (in dem die Zustände Potenzmengen der Zustände des NEAs sind), kann man das Problem also auf das Äquivalenzproblem von DEAs beschränken. Und dieses ist meiner Meinung nach entscheidbar (zur Not muß man halt die Sprachen konstruieren (durch Analyse der Automaten, das geht), in eine Normalform bringen (das geht auch) und vergleichen, aber das ist keine "schöne" Lösung).
Neue Frage »
Antworten »



Verwandte Themen



MatheBoard » Schulmathematik » Sonstiges » Äquivalenzproblem