Aus PDA Kontextfreie Grammatik erzeugen |
20.01.2013, 19:51 | Auf diesen Beitrag antworten » |
deppensido | Aus PDA Kontextfreie Grammatik erzeugen Hallo, zu der Aufgabe im Anhang habe ich folgende Lösung, kann bitte jemand schauen ob das so stimmt, ich bin mir etwas unsicher. S:= Q0Q3 Eingabealphabet:= { 0,1 } V = { Q0Q1, Q1Q1, Q1Q2, Q2Q2, Q2Q3, S, A, B} dabei heißt z.B.: Q1Q2 Übergang von Q1 nach Q2 Produktionen: S -> Q0Q1 Q2Q3 Q0Q1 -> Q0Q1 Q1Q1 Q1Q1 -> Q1Q2 Q1Q1 | Epsilon (leere Wort) Q1Q2 -> Q1Q2 Q2Q2 | AQ1Q1B | BQ1Q1A A -> 0 | Epsilon B -> 1 | Epsilon Q2Q2 -> Q2Q2 Q1Q2 | Epsilon | AQ1Q1B | BQ1Q1A Q2Q3 -> Q2Q2 Q2Q3 | Espilon Vielen Dank schon mal |
|
|
21.01.2013, 17:50 | Auf diesen Beitrag antworten » |
Karlito | Ich komme leider erst morgend dazu, mich darum zu kümmern. VG, Karlito |
22.01.2013, 12:56 | Auf diesen Beitrag antworten » |
Karlito | Hallo, müsst ihr die Grammatik aus dem Automaten konstruieren? Also habt ihr eine Konstrulktionsvorschrift wie man aus einem Automaten eine Grammatik erstellt? Wenn nicht: Welche Sprache wird vom dem Automaten erzeugt? Ich glaube die Grammatik lässt sich in genau einer Zeile beschreiben. VG. Karlito |
22.01.2013, 14:22 | Auf diesen Beitrag antworten » |
deppensido | hallo, wir sollen mit Hilfe des Beweises zum Lemma das besagt, dass aus jedem PDA eine Kontextfreie Grammatik erzeugt werden kann, die Grammatik konstruieren. Der Beweis ist natürlich sehr abstrakt und ich hab mich möglicherweise bei der Umsetzung vertan. |
Anzeige | |
|
|
22.01.2013, 16:26 | Auf diesen Beitrag antworten » |
Karlito | Hat das Lemma einen bestimmten Namen? Ich kenne es leider nicht. VG, Karlito |
22.01.2013, 16:35 | Auf diesen Beitrag antworten » |
deppensido | Naja, es hat nur eine Nummer. Ich könnte dir das Script per Mail schicken, da PDFs ja nicht hochgeladen werden können. |
22.01.2013, 19:37 | Auf diesen Beitrag antworten » |
Karlito | Habe den Skript gefunden. Ich schau mir das morgen mal an. Heute Abend ist mir das zu anstrengend. VG, Karlito |
24.01.2013, 21:21 | Auf diesen Beitrag antworten » |
Karlito | Habe es versucht, aber es bisher auch noch nicht geschafft mich da durch zu kämpfen, sorry. Wenn ich mehr weiß, schreibe ich es hier. VG, Karlito |
24.01.2013, 22:59 | Auf diesen Beitrag antworten » |
deppensido | ja, es ist wirklich kompliziert durch den Beweis richtig durchzublicken. In der Musterlösung wurde der PDA vereinfacht, womit einige Produktionen erspart blieben. Kann aber nicht daraus ableiten, ob meine Lösung jetzt richtig oder falsch ist. Grüße |
24.01.2013, 23:09 | Auf diesen Beitrag antworten » |
Karlito | Ich werde mir den Beweis bei Gelegenheit noch einmal anschauen. Finde es nicht uninteressant. Das Prinzip der Konstruktion scheint recht einfach, Bei der Umsetzung hapert es bei mir aber leider noch. Liegt sicher daran, dass ich das meist am Abend angehe und da auch nicht mehr die erforderliche Energie da ist. Wenn du eine Lösung hast, würde sie mich interessieren. VG, Karlito |
|