Archiv verlassen und diese Seite im Standarddesign anzeigen : Zustandsdiagramm - Formale Methoden
Hallo!!!
Und schon wieder komme ich bei der Klausurvorbereitung nicht weiter :-( . Diesmal geht es nicht um die Grammatik, sondern um ein Zustandsdiagramm.
Wir sollen folgende Formel als Zustandsdiagramm darstellen und irgendwie stehe ich auf dem Schlauch:(x | epsilon) (y x | y)*
Diese epsilon-Sache (entspricht dem "leeren Wort") bereitet mir ein Problem, denn ich kann ja kein Zustandsdiagramm aufstellen, wo epsilon den Zustandübergang darstellt. Oder ist es dem nicht so?
Vielen Dank im Voraus!!!
Mfg Djon
Stone2001
2006-07-23, 11:39:10
Erstmal: Was verstehst du unter Zustandsdiagramm? Einen deterministischen / indeterministischen endlichen Automaten? Mealy / Moore Automaten? Oder einfach nur etwas, was nicht näher spezifiziert ist?
Und die Epsilon Sache muß nicht unbedingt ein Problem sein. Ein Epsilon-Übergang wäre zwar formal nur in Chomsky Typ 0 zulässig, meistens wird aber eine Ausnahme gemacht unter der Einschränkung, das das leere Wort nur vom Startsymbol aus abgeleitet werden darf.
Hallo!!!
Also es muss ein deterministischer endlicher Automat werden. Da epsilon nur Anfang des Wortes vorkommen kann, darf ich es aus dem Startzustand (Z0) ableiten. Kann ich dabe epsilon als Zustandsübergang ansehen?
Mfg Djon
Stone2001
2006-07-23, 12:21:34
Djon[/POST]']Also es muss ein deterministischer endlicher Automat werden. Oki!
Djon[/POST]']
Da epsilon nur Anfang des Wortes vorkommen kann, darf ich es aus dem Startzustand (Z0) ableiten.
Yup, oder (je nach Definition) du kommst direkt mit Epsilion in den Startzustand, der wiederum gleich Endzustand ist.
Djon[/POST]']
Kann ich dabei epsilon als Zustandsübergang ansehen?
yup, das Auftauchen von Epsilion bewirkt auch einen Zustandsübergang (hier nur zum Startzustand).
Der Automat zu konstruieren ist dann ja nicht weiter schwierig.
So, habe jetzt eine kleine Skizze des Automaten gemacht, ohne dabei den epsilon-Übergang darzugstellen. Ich denke mir, dass es richtig ist.
Stone2001
2006-07-23, 13:13:22
Der Automat ist nicht korrekt!
Du befindest dich in Zustand Z2, dann kommst du mit x wieder zu Z2, damit akzeptiert der Automat eine beliebige Anzahl von x, was die Sprache aber nicht vorsieht.
Ein korrekter Automat könnte so aussehen:
M = (Z, Sigma, Delta, Z0, E), wobei
Z = {Z0, Z1, Z2}
Sigma = {Epsilon, x, y}
E = {Z1, Z2}
d(Z0, Epsilon) = Z1
d(Z0, x) = Z1
d(Z1, x) = Z2
d(Z1, y) = Z1
d(Z2, y) = Z1
Den Fehler habe ich jetzt auch entdeckt. Aber dein Automat würde auch eine Folge von x erkennen oder? Denn wenn im Z0 ist, kann er wieder ein x erkennen und das ist ja leider falsch. Welche Zustände sind bei deinem Automaten Endzustände?
Hier ist mein neues Diagramm:d(Z0, Epsilon) = Z1
d(Z0, x) = Z1
d(Z1, y) = Z2
d(Z2, y) = Z2
d(Z2, x) = Z1
Endzustäden sind dabei: Z1 und Z2
Stone2001
2006-07-23, 13:48:11
Stimmt ganz korrekt ist er immer noch nicht! Nächster Versuch:
M = (Z, Sigma, Delta, Z0, E), wobei
Z = {Z0, Z1, Z2}
Sigma = {Epsilon, x, y}
E = {Z1, Z2}
d(Z0, Epsilon) = Z1
d(Z0, x) = Z1
d(Z1, y) = Z2
d(Z2, y) = Z2
d(Z2, x) = Z1
Also wir können vom Startzustand Z0 nach Z1 mit Epsilon oder x. Dort können wir entweder das Wort akzeptieren oder ein y einlesen. Mit y kommen wir dann nach Z2. Dort können wir beliebig oft y einlesen. Bei einem x bekommen wir einen Übergang zu Z1. Dort können wir wieder mit y zurück zu Z2 wechseln.
Ok, die gleiche Idee, wie ich die schon davor gepostet habe :biggrin:
Na gut, ich werde hoffen, dass morgen in der Klausur so was ähnliches kommt. Zumindest bin jetzt, was die Epsilon-Regel angeht, etwas schauer. Danke!!!
PS: ich habe hier noch eine Frage und zwar bereitet mir eine Grammatik sehr viele Sorgen. Die Aufgabe ist es, eine Grammatik zu schreiben, die Wörter mit folgenden Eigenschaften erzeugt:mind. 2 Zeichen
Zeichen sind: x, y
beliebige Reihenfolge
das 4. Zeichen von rechts muss ein y seinDie Grammatik muss reguläre sein (Typ3).
Ich habe schon mehrfach versucht, doch leider kommt meine Grammatik nicht durch den Cup durch. Wenn ich diese von links mache, also das 4. Zeichen von links ein y, dann geht es ohne Probleme, doch andersrum kriege ich nur Shift/Reduce - Konflikte.
Vielleicht hast du eine Idee, wie man das Problem lösen kann.
Stone2001
2006-07-23, 14:15:04
Djon[/POST]']
PS: ich habe hier noch eine Frage und zwar bereitet mir eine Grammatik sehr viele Sorgen. Die Aufgabe ist es, eine Grammatik zu schreiben, die Wörter mit folgenden Eigenschaften erzeugt:mind. 2 Zeichen
Zeichen sind: x, y
beliebige Reihenfolge
das 4. Zeichen von rechts muss ein y seinDie Grammatik muss reguläre sein (Typ3).
Ich habe schon mehrfach versucht, doch leider kommt meine Grammatik nicht durch den Cup durch. Wenn ich diese von links mache, also das 4. Zeichen von links ein y, dann geht es ohne Probleme, doch andersrum kriege ich nur Shift/Reduce - Konflikte.
Vielleicht hast du eine Idee, wie man das Problem lösen kann.
Was ist bei dir Cup? Damit kann ich im Augenblick nichts anfangen.
Ansonsten würde ich folgenden Grammatik vorschlagen:
S -> BA
A -> x | y
B -> CA | A
C -> DA | A
D - > y | Ey
E -> EA | A
CUP ist ein Parsergenerierungs-Werkzeug. Ich benutze unter Windows java_cup und es gibt noch JLex für die Scanner-Generierung. Ich werde gleich mal deine Grammatik damit testen.
Edit: leider funktioniert deine Grammatik nicht, CUP meldet sehr viele Shift/Reduce-Konfllikte. Und die Grammatik muss regulär sein, also nur max. ein Nichtterminalsymbol auf der rechten Seite. Also ich finde, die Aufgabe ist echt gemein.
Stone2001
2006-07-23, 14:25:15
Aha, wieder etwas gelernt! Aber warum muß ich gerade an Compilerbau denken... ;)
Stone2001
2006-07-23, 14:30:04
Djon[/POST]']Edit: leider funktioniert deine Grammatik nicht, CUP meldet sehr viele Shift/Reduce-Konfllikte. Und die Grammatik muss regulär sein, also nur max. ein Nichtterminalsymbol auf der rechten Seite. Also ich finde, die Aufgabe ist echt gemein.
Das auf der rechten Seite nur ein Nichtterminalsymbol sein kann ist meines Wissens nach keine Einschränkung von regulären Grammatiken. Aber egal, die obige Grammatik kann man ja recht einfach dahingehend umwandeln:
S -> Bx | By
B -> Cx | Cy | x | y
C -> Dx | Dy | x | y
D - > y | Ey
E -> Ex | Ey | x | y
Wie sieht es nun hiermit aus?
Sieht ebenfalls schlecht aus :frown:
Hier ist der Auszug aus der Fehlermeldung, die CUP an der Stelle bringt:Building parse tables...
Computing non-terminal nullability...
Computing first sets...
Building state machine...
Filling in tables...
*** Reduce/Reduce conflict found in state #1
between B ::= x (*)
and E ::= x (*)
under symbols: {y, x}
Resolved in favor of the first production.
*** Reduce/Reduce conflict found in state #1
between B ::= x (*)
and C ::= x (*)
under symbols: {y, x}
Resolved in favor of the first production.
*** Shift/Reduce conflict found in state #1
between B ::= x (*)
under symbol y
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #1
between B ::= x (*)
under symbol x
Resolved in favor of shifting.
*** Reduce/Reduce conflict found in state #1
between E ::= x (*)
and C ::= x (*)
under symbols: {y, x}
Resolved in favor of the second production.
*** Shift/Reduce conflict found in state #1
between E ::= x (*)
under symbol y
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #1
between E ::= x (*)
under symbol x
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #1
between C ::= x (*)
under symbol y
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #1
between C ::= x (*)
under symbol x
Resolved in favor of shifting.
*** Reduce/Reduce conflict found in state #15
between D ::= E y (*)
and E ::= E y (*)
under symbols: {y, x}
Resolved in favor of the first production.
*** Shift/Reduce conflict found in state #15
between D ::= E y (*)
under symbol y
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #15
between D ::= E y (*)
under symbol x
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #15
between E ::= E y (*)
under symbol y
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #15
between E ::= E y (*)
under symbol x
Resolved in favor of shifting.
*** Reduce/Reduce conflict found in state #7
between E ::= y (*)
and C ::= y (*)
under symbols: {y, x}
Resolved in favor of the second production.
*** Reduce/Reduce conflict found in state #7
between E ::= y (*)
and B ::= y (*)
under symbols: {y, x}
Resolved in favor of the second production.
*** Reduce/Reduce conflict found in state #7
between E ::= y (*)
and D ::= y (*)
under symbols: {y, x}
Resolved in favor of the second production.
*** Shift/Reduce conflict found in state #7
between E ::= y (*)
under symbol y
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #7
between E ::= y (*)
under symbol x
Resolved in favor of shifting.
*** Reduce/Reduce conflict found in state #7
between C ::= y (*)
and B ::= y (*)
under symbols: {y, x}
Resolved in favor of the second production.
*** Reduce/Reduce conflict found in state #7
between C ::= y (*)
and D ::= y (*)
under symbols: {y, x}
Resolved in favor of the first production.
*** Shift/Reduce conflict found in state #7
between C ::= y (*)
under symbol y
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #7
between C ::= y (*)
under symbol x
Resolved in favor of shifting.
*** Reduce/Reduce conflict found in state #7
between B ::= y (*)
and D ::= y (*)
under symbols: {y, x}
Resolved in favor of the first production.
*** Shift/Reduce conflict found in state #7
between B ::= y (*)
under symbol y
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #7
between B ::= y (*)
under symbol x
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #7
between D ::= y (*)
under symbol y
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #7
between D ::= y (*)
under symbol x
Resolved in favor of shifting.
Checking for non-reduced productions...
*** Production "E ::= y " never reduced
*** Production "E ::= x " never reduced
*** Production "E ::= E y " never reduced
*** Production "D ::= y " never reduced
*** Production "C ::= y " never reduced
*** Production "C ::= x " never reduced
Stone2001
2006-07-23, 15:13:41
Haben wir einen Compilerbauer hier? Compilerbau habe ich zwar gehört, aber nie prüfen lassen und demzufolge habe ich mich mit den theoretischen Konstrukten dazu nie wirklich befasst. LALR oder LR Grammatiken sind übel.
Aber nächster Versuch:
Dies ist wohl die Grammatik die du oben schon erwähnt hast (das y ist das 4. Zeichen von links):
S -> xA | yA
A -> xB | yB | x | y
B -> xC | yC | x | y
C -> yD | y
D -> xD | yD | x | y
Aber wie sieht folgende Grammatik aus?
S -> xA | yA | yY | yC | xC
A -> xB | yB | yY
B -> xA | yA | yY
C -> x | y | xD | yD
D -> x | y
Y -> xY1 | yY1
Y1 -> xY2 | yY2
Y2 -> x | y
Was soll ich sagen, wieder das gleiche Ergebnis:*** Reduce/Reduce conflict found in state #14
between D ::= y (*)
and Y2 ::= y (*)
under symbols: {EOF}
Resolved in favor of the first production.
*** Shift/Reduce conflict found in state #14
between D ::= y (*)
under symbol EOF
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #14
between Y2 ::= y (*)
under symbol EOF
Resolved in favor of shifting.
*** Reduce/Reduce conflict found in state #9
between Y2 ::= x (*)
and D ::= x (*)
under symbols: {EOF}
Resolved in favor of the second production.
*** Shift/Reduce conflict found in state #9
between Y2 ::= x (*)
under symbol EOF
Resolved in favor of shifting.
*** Shift/Reduce conflict found in state #9
between D ::= x (*)
under symbol EOF
Resolved in favor of shifting.Ich nehme an, dass die Aufgabenstellung falsch ist, denn ich kann mir überhaupt nicht vorstellen, warum das Ding nicht durch den CUP geht :mad:
Das Fach heisst bei uns "Formale Methoden" und da haben wir diese beiden Werkzeuge kennengelernt und habe diese auch im Labor angewenden müssen.
Was studierst du genau?
Stone2001
2006-07-23, 16:02:30
Djon[/POST]']Ich nehme an, dass die Aufgabenstellung falsch ist, denn ich kann mir überhaupt nicht vorstellen, warum das Ding nicht durch den CUP geht :mad:
Naja, die Frage ansich ist ja nicht besonders schwer. Nur CUP kommt mit indeterminismen nicht besonders zurecht. ;)
Falls du mal eine korrekte Lösung findest, poste sie hier, würde mich auch mal interessieren, wie die aussieht.
Djon[/POST]']
Das Fach heisst bei uns "Formale Methoden" und da haben wir diese beiden Werkzeuge kennengelernt und habe diese auch im Labor angewenden müssen.
Was studierst du genau?
Ich studiere (noch) Informatik. Wir hatten Theoretische Informatik in Info III (da gings es gerade um Sprachen und Co) und im Hauptdiplom in Formale Systeme (da geht es aber mehr um Logiken).
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.