| Die letzten 10 Beiträge |
| 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 |
| 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? |
| 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 |
| 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 |
| 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 |
| 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? |
| 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 |
| 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. 
|
| 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! |
| 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.
![[latex]<br />
\begin{array}{c|c|c|c}<br />
Z & a & b & c<br />
\hline \{q_0\} & \{q_0,q_2\} & \{q_0,q_1\} & \{q_1,q_2\}<br />
\{q_0,q_2\} & \{q_0,q_2\} & \{q_0,q_1\} & \{q_1,q_2\}<br />
\{q_0,q_1\} & \{q_0,q_2\} & \{q_0,q_1\} & \{q_1,q_2\}<br />
\{q_1,q_2\} & \{q_2\} & \{q_1\} & \{q_1,q_2\}<br />
\{q_1\} & \{q_2\} & \{q_1\} & \{q_1,q_2\}<br />
\{q_2\} & \{q_2\} & \{\} & \{q_2\}<br />
\{\} & \{\} & \{\} & \{\}<br />
\end{array}<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
\begin{array}{c|c|c|c}<br />
Z & a & b & c<br />
\hline \{q_0\} & \{q_0,q_2\} & \{q_0,q_1\} & \{q_1,q_2\}<br />
\{q_0,q_2\} & \{q_0,q_2\} & \{q_0,q_1\} & \{q_1,q_2\}<br />
\{q_0,q_1\} & \{q_0,q_2\} & \{q_0,q_1\} & \{q_1,q_2\}<br />
\{q_1,q_2\} & \{q_2\} & \{q_1\} & \{q_1,q_2\}<br />
\{q_1\} & \{q_2\} & \{q_1\} & \{q_1,q_2\}<br />
\{q_2\} & \{q_2\} & \{\} & \{q_2\}<br />
\{\} & \{\} & \{\} & \{\}<br />
\end{array}<br />
)
Im Anhang findest Du noch die Bilder zu den einzelnen Automaten.
Gruß,
Karlito
Karlito hat diese Bilder (verkleinerte Versionen) angehängt:
  
|
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
|
|
