Informatiker Board | Druckvorschau: NFA konstruieren

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Automatentheorie (http://www.informatikerboard.de/board/board.php?boardid=13)
----- NFA konstruieren (http://www.informatikerboard.de/board/thread.php?threadid=2547)

Geschrieben von Schattenklinge am 07.11.2015 um 14:14:

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!

Geschrieben von Karlito am 07.11.2015 um 15:07:

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

Geschrieben von Schattenklinge am 08.11.2015 um 11:43:

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...

Geschrieben von Karlito am 09.11.2015 um 10:45:

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

Geschrieben von Karlito am 10.11.2015 um 13:51:

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.

$[latex] \begin{array}{c|c|c|c} Z & a & b & c \hline \{q_0\} & \{q_0,q_2\} & \{q_0,q_1\} & \{q_1,q_2\} \{q_0,q_2\} & \{q_0,q_2\} & \{q_0,q_1\} & \{q_1,q_2\} \{q_0,q_1\} & \{q_0,q_2\} & \{q_0,q_1\} & \{q_1,q_2\} \{q_1,q_2\} & \{q_2\} & \{q_1\} & \{q_1,q_2\} \{q_1\} & \{q_2\} & \{q_1\} & \{q_1,q_2\} \{q_2\} & \{q_2\} & \{\} & \{q_2\} \{\} & \{\} & \{\} & \{\} \end{array} [/latex]$

Im Anhang findest Du noch die Bilder zu den einzelnen Automaten.

Gruß,

Karlito

Geschrieben von Schattenklinge am 12.11.2015 um 08:22:

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!

Geschrieben von Schattenklinge am 12.11.2015 um 08:23:

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. smile

Geschrieben von Karlito am 12.11.2015 um 13:10:

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

Geschrieben von Schattenklinge am 13.11.2015 um 22:10:

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?

Geschrieben von Karlito am 14.11.2015 um 00:45:

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

Geschrieben von Schattenklinge am 18.11.2015 um 19:29:

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

Geschrieben von Karlito am 19.11.2015 um 15:42:

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

Geschrieben von Schattenklinge am 20.11.2015 um 09:26:

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?

Geschrieben von Karlito am 20.11.2015 um 12:44:

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