Weiß auch noch nicht, wie es weiter geht.
Aber kann es sein, dass G1 falsch beschrieben wurde und in Wirklichkeit
G1=({a,b},{S},S,{S->aSb,S->e}) ?!
Mir scheint,dass N und sigma vertauscht sind…
ist doch scheissegal ob [img]
http://mokrates.de/cgi-bin/texstring?(\{S\},\{a,b\},...)[/img] oder [img]
http://mokrates.de/cgi-bin/texstring?(\{a, b\},\{S\},…)[/img].
ist doch klar, dass [img]
http://mokrates.de/cgi-bin/texstring?\{S\}[/img] die menge der nicht-terminale und [img]
http://mokrates.de/cgi-bin/texstring?\{a,b\}[/img] die menge der terminale ist. wierum man das schreibt ist nur definitionssache, spielt aber für 'wie geht der beweis' keine rolle.
ich häng auch fest. ich weiß eigentlich genau worum es geht, mir fehlen nur die methoden es auszudrücken [28]
Ein guter Kandidat für den ersten Schritt ist immer, die Definition anzusehen.
Es soll ja bewiesen werden, dass die von der Grammatik erzeugte Wortmenge
mit der Menge [latex]L_1[/latex] übereinstimmt. Es soll also gezeigt werden,
dass ein Wort genau dann abgeleitet werden kann, wenn es in [latex]L_1[/latex] enthalten
ist. In dem Fall ist also die Definition der von einer kontextfreien Grammatik
erzeugten Sprache nützlich.
Die sagt ja: Ein Wort w kann genau dann abgeleitet werden,
wenn es eine Folge [latex]S\Rightarrow w_1\Rightarrow\cdots\Rightarrow w_k\Rightarrow w[/latex]
gibt. Dann muss man sich natürlich ansehen, wie die Relation
[latex]\Rightarrow[/latex] definiert ist, usw. Dann kann man beweisen, dass ein Wort
genau dann erzeugt wird, wenn es in [latex]L_1[/latex] enthalten ist. Und
dafür bietet sich z.B. Induktion an.
Hilft das weiter?
ja, danke :)
mit induktion hab ich auch schon rumgespielt, immerhin weiß ich jetzt dass die richtung nicht falsch war :)
Habe es so gemacht , dass ich zunächst L1 teilmenge L(G1) zeige, in dem ich beweise, dass für jedes w aus L1 ein S=>* w' aus L(G1) existiert mit w=w' , in anderen worten zeigt man dass es für jedes wort aus L1 eine Ableitung gibt.
Im zweiten fall L(G1) teilmenge L1 , zeige ich , dass sich unter der Grammatik G1 nur w erzeugen lassen, die auch in L1 liegen.
ich hab mal ne generelle Frage. wie drückt man folgendes formal korrekt bzw. optimalerweise sogar mit tollen Formelsymbolen aus:
[latex]w_n[/latex] ist ein wort aus [latex]L(G_1)[/latex] welches entsteht, wenn [latex]S\rightarrow{}aSb[/latex] n-mal und danach [latex]S\rightarrow{}\epsilon[/latex] einmal ausgeführt wird.
Hm, anscheinend wurde kein Formalismus eingeführt um
zu beschreiben, welche Regel bei einem Ableitungsschritt
angewandt wird. Deswegen würde ich das einfach so sagen:
Sei [latex]w_n[/latex] ein Wort, das in n+1 Schritten aus S abgeleitet werden
kann, wobei in den ersten n Schritten die Regel [latex]S\rightarrow aSb[/latex]
und im letzten Schritt die Regel [latex]S\rightarrow\epsilon[/latex] angewendet wird.
könnte mal jemand zeigen, wie man einen induktionsbeweis formal korrekt aufschreibt?
ich habe probleme das zu fomulieren….
Habe es so gemacht , dass ich zunächst L1 teilmenge L(G1) zeige, in dem ich beweise, dass für jedes w aus L1 ein S=>* w' aus L(G1) existiert mit w=w' , in anderen worten zeigt man dass es für jedes wort aus L1 eine Ableitung gibt.
Im zweiten fall L(G1) teilmenge L1 , zeige ich , dass sich unter der Grammatik G1 nur w erzeugen lassen, die auch in L1 liegen.
wie genau zeigst du das? ich verstehe ja alles was hier so gesagt wurde, aber wie bringe ich nun all dies zusammen in eine form, die dann der beweis und somit die lösung der aufgabe ist?
ich könnte dies alles gut mit worten erklären aber wie schreibe ich es auf?
kann mir jemand helfen? ich könnte ja bis zur übung warten aber dann bekomme ich ja keine punkte mehr. brauche dringend eine einstiegshilfe.
