 NFA konstruieren |
Schattenklinge
unregistriert
 |
|
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 14:14 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
07.11.2015 15:07 |
|
|
Schattenklinge
unregistriert
|
|
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...
|
|
|
08.11.2015 11:43 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
09.11.2015 10:45 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
|
|
10.11.2015 13:51 |
|
|
Schattenklinge
unregistriert
|
|
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:22 |
|
|
Schattenklinge
unregistriert
|
|
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 08:23 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
12.11.2015 13:10 |
|
|
Schattenklinge
unregistriert
|
|
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?
|
|
|
13.11.2015 22:10 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
14.11.2015 00:45 |
|
|
Schattenklinge
unregistriert
|
|
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
|
|
|
18.11.2015 19:29 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
19.11.2015 15:42 |
|
|
Schattenklinge
unregistriert
|
|
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 09:26 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
20.11.2015 12:44 |
|
|
|
