 Aus PDA Kontextfreie Grammatik erzeugen |
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
 |
|
| 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
deppensido hat dieses Bild (verkleinerte Version) angehängt:
|
|
20.01.2013 19:51 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Ich komme leider erst morgend dazu, mich darum zu kümmern.
VG,
Karlito
|
|
|
21.01.2013 17:50 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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 12:56 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
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.
|
|
|
22.01.2013 14:22 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hat das Lemma einen bestimmten Namen? Ich kenne es leider nicht.
VG,
Karlito
|
|
|
22.01.2013 16:26 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
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 16:35 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Habe den Skript gefunden. Ich schau mir das morgen mal an. Heute Abend ist mir das zu anstrengend.
VG,
Karlito
|
|
|
22.01.2013 19:37 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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 21:21 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
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 22:59 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
24.01.2013 23:09 |
|
|
|
