Verzweifle gerade an 10.2.

Folgende Aufgabe:

P := {(S,),(S,SS),(S,lambda)}

(also offensichtlich eine Grammatik für die Dyck-Sprache, wenn mich nicht alles täuscht).

Die Aufgabe lautet nun folgendermaßen: "Konstruieren Sie mit dem Verfahren aus dem Skript eine äquivalente, kontextfreie Grammatik ohne Linksrekursion.

Ich bin ja der Meinung, dass das richtige Ergebnis - gemäß der alternativen Schreibweise der Dycksprache aus dem Skript - folgendermaßen aussehen müsste:

S-> aSbS | lambda

Das Problem ist nur, dass ich es nicht hinbekomme ein Ergebnis, das dem obigen zumindest ähnlich ist, mit dem Verfahren zur Vermeidung von Linksrekursion zu erzielen… Außerdem bin ich nicht sicher, ob das "Sb" aus "aSbS" doch noch linksrekursiv ist. Vielleicht kann mir jemand einen Tipp geben…

schau doch einfach mal im skript, was da unter linksrekursiv steht (und in der Nähe) …

mal ne andere frage: hat jemand 10.2 b) geschafft? (ist das überhaupt möglich?)

Ich hätte da auch noch ein Problem:

In der gleichen Aufgabe unter Punkt (b) heisst es:
Beweisen Sie, dass das Komplement der Menge D(a,b) (Anm.: D(a,b) gleich der Dyck-Sprache), also die Menge

{w element {a,b}+ | w nicht element D(a,b)}

kontextfrei ist, indem Sie eine kontextfreie Grammatik dafür angeben!

Ich habe nicht viele Ideen für einen Ansatz… Reicht es eine Grammatik zu finden, die eine andere Sprache erzeugt? Das wäre ja schon eine Grammatik, die mit einem b anfängt, oder? Oder bin ich da total auf dem Holzweg??? Hiiiiiiilfeeee!!!

Das wäre dann aber nicht das Konplement, oder?!
Wieso eigentlich D(a,b)??

du sollst ja das komplement bilden uzw. mit den terminalen [,] die ja vorgegeben sind….

ich dachte könnte z.b. eine Menge sein die soetwas enthält??!:

1 [
2 ]
3 [[
4 ]]
5 ][
6 [[[
7 ]]]
8 [][
9 []]
10 ][]
…. usw…

Zur Aufgabe (b):

Was wäre denn dann das Komplement? Die Menge aller unkorrekt geklammerten Ausdrücke (Halt komplementär zu der Menge aller korrekt geklammerten Ausdrücke)?
Und D(a,b) statt D([,])…

Zur Aufgabe (a):

Ich meine mir die Sachen im Skript (und in der Nähe) angesehen zu haben… nur den Clou habe ich daraus nicht gewinnen können… ist in "aSb" das "Sb" nun eine linksrekursion? und was passiert nach dem verfahren mit "SS"? da ist doch keine linksrekursion enthalten, oder ?

????????????????????????????ßßßß

zu a)
also ich habe es ohne die dyck-sprache gemacht, sondern dass verfahren(beweis) aus dem script angewendet (weiß aber nicht ob das so richtig ist)…

zu Aufgabe 10.2 (a)

Mit welchem Verfahren kommt amn denn zum Ergebnis??
Mit dem Algorithmus von 4.30 Seite 105 im Skript??

Oder bin ich damit auf dem Holzweg?

Gruß

4.30 hat damit meines erachtens gar nichts mehr zu tun, den da dreht es sich um die Greibach Normalform und nicht um Linksrekursivität. Schau doch mal auf die andere Seite 104… :) (linksrekursion)

ok. sehe ich ein…

Ich habe das nun mal gemacht… und bekomme eine nicht endende CFG raus, da ich sowas wie "S -> lambda Sdach" konstruiert habe und…

Kann mit da mal einer nen tip geben, was ich mit lambda mache??

Gruß

Mir scheint es so als ob sich gerade bei Fragen zu F2 alle erstmal ausloggen, weil sie wissen das Jansen hier auch öfter mal reinschaut und sich manchmal über die blöden Fragen ärgert. Aber vielleicht hab ich gestern auch einfach zu viel billigen Fussel gesoffen!? [img]http://www.fb18.de/gfx/bounce.gif[/img]

Da ich bis gerade eben noch keinen Account hier hatte, habe ich als "Anonymer User" gepostet…

Nun habe ich einen und würde mich über Antworten zu meinen Problem (siehe zwei Antowrten vorher) freuen.

Gruß
Heitzman

mhhh die regel haben wir auch, aber es geht doch trotzdem… (Regel S->lambda bleibt doch auch in der Menge)

nimmt man also die verbleibenden nicht linksrekursiven Produktionen wieder mit in die Menge hinein???

Ja, steht so im Algorithmus:

Eine neue CFG G' […] wird aus G gebildet durch Hinzufügen des neuen Nonterminals /A und Ersetzen aller linksrekursiven A-Produktionen von G durch […]

zurück zur frage 10.2 (b) hat das jemand geschafft???

Ich habe eine Grammatik und denke, sie könnte richtig sein. Aber ob sie das wirklich ist, steht in den Sternen (und das Problem ist, ich weiß nicht an welcher Stelle – vermutlich irgendwo, so dass man es von Hamburg nicht lesen kann).

Zum Ansatz: Überlegen, was für Worte gelten muss, die nicht in der gegebenen Sprache sind, also falsch geklammert sind (was ist wenn an dieser Stelle eine Klammer mehr steht, was passiert wenn ich jene Klammer umdrehe, …). Und ein bisschen (viel) experimentieren und auf die zündende Idee warten, die dann die Grammatik darstellt (ist halt blöd zu beschreiben, ohne die (vermeintliche) Lösung zu verraten). Vielleicht so viel noch: Eine Klammerung ist dann falsch, wenn sie aus einer korrekten Klammerung besteht und noch eine Klammer dazu kommt, oder zwei, die falsch gesetzt sind. Eine Klammerung ist auch falsch, wenn eine falsche Klammerung nochmal korrekt geklammert wird.

Mut zur Farbe.

Das was du geschrieben hast hab ich mir auch schon überlegt und mindestens 20.000 verschiedene Ansätze gehabt, die jedoch ALLE widerlegt……. solangsam nervt es einfach nur noch :(

wie viele produktionen hast du gebraucht?

Kann dich voll verstehen, Azreal. Im Prinzip ist es einem klar, was man haben will, aber das in eine Grammtik umzusetzen, ist gleich etwas ganz Anderes. Irgendwo hakt's immer, wenn man mal grade wieder augenscheinlich auf einen tollen Ansatz gekommen ist.

ich brauche 6 Produktionen bei (b)

Habe 9 Produktionen. Aber man kann ja oft ohne weiteres noch ein paar mehr oder weniger machen und man hat immer noch eine äquivalente Grammatik. Insofern ein schlechter Anhaltspunkt.

Eine Klammerung ist auch falsch, wenn eine falsche Klammerung nochmal korrekt geklammert wird.

Leider nicht ganz….][ ist eine falsche Klammerung…wenn ich diese korrekt einklammer, komme ich auf [][], was wieder richtig ist…

Hast gewonnen. Dann ist meine Grammatik wohl so ziehmlich falsch.

Wir hams aber auch nicht…entweder es hakte an [][] oder daran, daß Konstrukte wie [[[] nicht erzeugt werden konnten…stinkt alles [img]http://www.fb18.de/gfx/19.gif[/img]