NFA konstruieren |
| 07.11.2015, 14:14 | Auf diesen Beitrag antworten » |
| Schattenklinge | NFA konstruieren Hallo, ich soll einen NFA konstruieren, welcher die Sprache: L = {a,b}^* {b,c}^* {a,c}^* Ich habe zurzeit den Automaten folgendermaßen entworfen: q0 ----Epsilon----> q1 ----Epsilon----> q2 wobei q0 auf sich selbst zeigt mit a,b, q1 auf sich selbst zeigt mit b,c, und q2 auf sich selbst zeigt mit a,c. Ist das richtig? Viele Grüße und schönen Dank schonmal! |
|
|
|
| 07.11.2015, 15:07 | Auf diesen Beitrag antworten » |
| Karlito | Kann man so machen. Die Frage ist nur, ob Epsilon-Übergänge erlaubt sind. Bei uns wurde noch zwischen NFA und Epsilon-NFA unterschieden. Weiterhin musst Du noch den Startzustand und die Menge der Finalzustände angeben. Gruß, Karlito |
| 08.11.2015, 11:43 | Auf diesen Beitrag antworten » |
| Schattenklinge | Ja, epsilon-transitionen sind erlaubt, ich soll dazu noch einen DFA konstruieren mittels Potenmengenkonstruktion, wie viele Zustände brauch ich dann? Ich hab derzeit 3, einmal startzustand, die potenzmenge, die bestehend aus allen drei zuständen ist, weil ich ja über die Epsilonzustände vom Startzustand aus alle erreichen kann... Dann noch einen Trap-Zustand von startzustand, aber ob man den wirklich braucht... |
| 09.11.2015, 10:45 | Auf diesen Beitrag antworten » |
| Karlito | Kann ich nicht genau sagen. Dazu müsste ich erst den DFA erstellen. Dazu komme ich aber erst heute Abend oder Morgen. Um den DFA zu erstellen, muss man erst die Epsilon-Übergänge ersetzen und einen äquivalenten Epsilon-freien NFA erstellen. Daraus kann man dann den DFA konstruieren. Am besten geht das, indem man von jedem Zustand aus die Menge der Zustände notiert, die mit einer Eingabe erreichbar sind. Dies werden dann wieder neue Zustände (geht am Besten tabellarisch). Gruß, Karlito |
| Anzeige | |
|
|
|
| 10.11.2015, 13:51 | Auf diesen Beitrag antworten » |
| Karlito | So, also ich brauche 7 Zustände und hoffe, dass ich keinen Fehler gemacht habe. Hier die Tabelle für die Konstruktion des DFA. Jede Zustandsmenge, die einen Finalzustand des NFA enthält ist selbst wieder ein Finalzustand. Die leere Menge ist ein Papierkorbzustand, der alle ungültigen Eingaben behandelt. Im Anhang findest Du noch die Bilder zu den einzelnen Automaten. Gruß, Karlito |
| 12.11.2015, 08:22 | Auf diesen Beitrag antworten » |
| Schattenklinge | Hallo, danke dir für deine Mühe, ich komme auf dieselbe Tabelle allerdings sind bei mir alle 3 Zustände Finalzustände, weil ich kann auch garnichts schreiben, das würde der Automat auch akzeptieren, oder eben nur ein a oder ein c. Ich hab allerdings den Epsilon-NFA so gelassen wie er ist und habe ihn dann auch so in einen DFA umgewandelt bekommen... Natürlich hab ich dann nicht sowas wie a-transition sondern a,b-Transition, klappt aber auch wunderbar. Vielen Dank! |
| 12.11.2015, 08:23 | Auf diesen Beitrag antworten » |
| Schattenklinge | Was ich gerade noch bei deiner Lösung gesehen habe, bei dir fehlt die Potenzmenge: q0q1q2, denn die ist über Epsilon erreichbar, liegt aber daran, dass du den ersten Zustand nicht als Finalzustand hast. 
|
| 12.11.2015, 13:10 | Auf diesen Beitrag antworten » |
| Karlito | Epsilon-Übergänge sind im DFA nicht erlaubt. Mit den Finalzuständen hast Du natürlich recht. Wenn ich nicht noch etwas übersehen habe, führt das jedoch nur dazu, dass alle Zustände bis auf den Papierkorbzustand zu Finalzuständen werden. Gruß, Karlito |
| 13.11.2015, 22:10 | Auf diesen Beitrag antworten » |
| Schattenklinge | Okay, ich hab noch einen NFA zu konstruieren: Das Wort soll 3 oder mehr zeichen haben, muss auf aa, ab, ba enden, dazu darf nicht mehr als 5 Zustände verwendet werden... Bei mir hapert es an: Wort endet auf ab... Ich hab 5 zustände, aber irgendwie fehlt noch was womit ich mein Wort auf ab terminieren kann... Hast du vielleicht einen Tipp? |
| 14.11.2015, 00:45 | Auf diesen Beitrag antworten » |
| Karlito | Geh vom Ende des Wortes aus. Wir haben dann einen Finalzustand, der mit b endet und einen der mit a endet. Reicht das als Tipp? Gruß, Karlito |
| 18.11.2015, 19:29 | Auf diesen Beitrag antworten » |
| Schattenklinge | Habe es hinbekommen, vielen Dank, jetzt weiche ich mal vom Thema ab: Es geht um endliche Automaten und reguläre Ausdrücke: Ich soll einen DFA konstruieren, der diese reguläre Sprache akzeptiert: L = { w in {a,b}* | w nicht in {ba,ab}* } Das Problem ist erstmal diese Sprache zu verstehen, darf sie nicht die Teilwörter ab und ba haben? D.h. die Sprache die der DFA akzeptieren soll lautet z.b. aaabbb obwohl hier das Teilwort ab drin vorkommt, oder darf das Wort w nicht nur aus Teilfolgen ba oder ab bestehen? Wenn ich das weiß, kann ich vielleicht den FA konstruieren... Vielen dank schonmal |
| 19.11.2015, 15:42 | Auf diesen Beitrag antworten » |
| Karlito | Hallo Schattenklinge, ich bin anders herangegangen. Ich habe einen DFA für die Sprache L = {w in {ab,ba}*} entworfen und davon das Komplement gebildet. Beim Komplement einer regulären Sprache werden alle Finalzustände zu Nicht-Finalzuständen und umgekehrt (wenn ich mich recht erinnere). Gruß, Karlito |
| 20.11.2015, 09:26 | Auf diesen Beitrag antworten » |
| Schattenklinge | Den Trick muss ich mir merken! Danke! Dank dir kann ich mein Wissen gut erweitern oO, wundert mich, dass dieses Forum so "leer" und unbenutzt ist... Dann hab ich direkt noch eine Frage^^ Ich hab eine rechtslineare Grammatik gegeben, die nicht eindeutig ist, d.h. für ein Wort in der Sprache gibt es zwei Ableitungen, die auf das selbe Wort hinauslaufen. Wie kann ich daraus eine eindeutige Grammatik machen? Ich habe mir schon einen NFA dazu gezeichnet und bin gerade dabei den in DFA zu verwandeln, eventuell hilft mir das... Die Aufgabe ist es ein Verfahren zur konstruktion eindeutiger rechtslinearer Grammatik zu beschreiben... Derzeit bin ich noch am rumprobieren, ist das der richtige Weg oder gibt es noch einen einfacheren? |
| 20.11.2015, 12:44 | Auf diesen Beitrag antworten » |
| Karlito | Hallo Schattenklinge, der Grund dafür, dass das Forum so unbenutzt ist, ist dass es größtenteils nur zwei Autoren gibt, von denen ich nicht der fleißigste bin. Deine Herangehensweise ist formal schon nicht schlecht. Der NFA sollte sich ja aus der Grammatik ablesen lassen. Danach die Umwandlung in einen DFA und dieser muss dann minimiert werden. Der minimierte Automat ist dann bis auf Umbenennung der Zustände eindeutig. Daraus kann man wiederum die Grammatik ablesen. Ob es einen effektiveren Weg gibt, weiß ich leider nicht. Gruß, Karlito |
|
|
