Wie bildet man einen DEA aus dieser etwas komplizierteren Sprache?
Guten Abend,
ich sitze nun schon mehr als 3 Stunden an dieser Sprache inklusive Alphabet hier:
Hat Jemand eine Idee?
Klar ist, dass die Sprache entweder mit Lambda oder mit 11 oder mit 10 oder mit 00 terminiert. Nur bin ich gerade irgenwie nicht in der Lage etwas passendes zu finden, Fällt euch was schnelles ein?
Liebe Grüße
P.S. Es ist keine Hausaufgabe, also eine vollständige Lösung wäre auch erwünscht.
3 Antworten
Wechsel von q0 nach q1 für Eingabe 0, von q1 nach q2 für Eingabe 1 (jetzt dürfen wir nicht akzeptieren), für 0 wechsle auf q1 zurück, für 1 wechsle auf q0. Wird in q0 eine 1 gelesen verbleibe in q0. wenn wir in q1 stehen, für 1 wechsle in q0 zurück, für 0 verbleibe in q1.
q0 ist Startzustand und q0 und q1 akzeptieren.
Kommt das hin?
Ääääh, ja, da habe ich etwas doppelt - Im Prinzip wollte ich eigentlich jeanyfans Variante, wobei q1 und q2 genau vertauschte Rollen haben, der Übergang q1,1->q0 ist zu viel, ich hatte im ersten Satz schon gesagt, daß q1,1->q2 benötigt wird.
Hätte ich es besser mal kurz aufgeschrieben, statt nur im Kopf zu machen :-/.
Also ich hab es einfach folgendermaßen gelöst:
Konstruiere zunächst einen NEA, der alle w akzeptiert, die auf 01 enden. Das ist recht einfach:
Und wenn du jetzt die Endzustände vertauschst, akzeptiert dieser neue Automat grade die Komplementsprache des alten, also alle w, die nicht auf 01 enden:
Genau so hab ich es nun auch hinbekommen, dann stimmt wenigstens meine Lösung. Leider ist meine Aufgabe dennoch nicht erfüllt, denn eigentlich sollte ich erst die Äquivalenzklassen nach Myhill nerode bestimmen und dann die Klassenautomaten bauen
Wenn ich es richtig verstanden habe, geht es so:
Du hast die 3 Klassen [∊], [0] und [01].
In [∊] sind alle Wörter drin, die NICHT auf 01 oder 0 enden. Also das leere Wort und alle Wörter mit ner 1 hinten. Da führt das Anhängen von Wörtern, die auf 01 enden dann dazu, dass das Wort nicht in L ist, alle anderen Wörter sind in L.
In [0] sind alle Wörter drin, die auf 0 enden. Da führt das Anhängen von Wörtern, die auf 1 enden dann dazu, dass das Wort nicht in L ist, alle anderen Wörter sind in L.
In [01] sind alle Wörter drin, die auf 01 enden. Da führt das Anhängen von ∊ dazu, dass das Wort nicht in L ist, da es derzeit ja nicht akzeptiert wird, alle anderen Zeichen, die man anhängt, führen dann wieder zu einem Wort aus L.
Im Diagramm oben wäre dann q0= [∊], q1=[0] und q2=[01].
Weil die Wörter, die auf 0 enden, ne andere Klasse sind als die, die auf 1 enden. Die in der Klasse [∊] sind wie gesagt alle, die entweder leer sind oder auf 1 enden. Wenn du es unbedingt als Menge willst, müsste das
[∊] = { {0,1}^n 1^m | n in N; m in N, m>0} vereinigt mit epsilon sein.
Myhill nerode äquivalenzklassen bilden, dann hast du bereits deinen automaten
Hallo, genau das ist die eigentliche Aufgabe, nur bin ich nicht in der Lage solche Klassen zu bilden, ich verstehe das verfahren dahinter nicht und habe mir erhofft, dadurch die Aufgabe lösen zu können, bzw zu sehen wie ich auf die Klassen komme.
Könntest du mir erklären wie man diese Klassen bildet? Ich kenne den Wiki eintag und die Theorie dahinter, nur schaffe ich es nicht die Klassen zu bilden
Naja, du sagst qo und q1 sind Endzustände sowie qo ist ei Startzustand.
Weter sagst du gehe von q0 mit 0 zu q1, später sagst du noch "wenn wir in q1 stehen, für 1 wechsle in q0 zurück" ergo hätten wir qo->0 q1, q1->0q0 also 01, was nicht ein soll