Wie gibt man die Sprache einer (Grammatik) an?
Hi!
Wir haben gestern das Thema Grammatik begonnen und ich verstehe einfach nicht, wie man auf eine Sprache kommen soll.
Hier ein Beispiel (ist keine Hausaufgabe):
Klar ist, dass ich irgendwie die Ableitung bestimmen muss, nur wie kommt man dann auf die Sprache L(G1)?
Im Buch machen die das anhand der Ableitung, also sie lesen das an regelrecht ab.
Ich verstehe aber nicht, welche der vielen Möglichkeiten den die Sprache ergeben könnte. Hoff mein Problem ist etwas verständlich?
Irgendwie läuft es ja mittels regulärer Ausdrücke, oder?
Liebe Grüße Sandra
3 Antworten
reguläre Sprachen kannst du als reguläre Ausdrücke schreiben und es gibt einen passenden DFA dazu.
Auf den ersten Blick müßte das Beispiel rechtsregulär sein.
Wenn dem so ist, kann man für diese Produktionen natürlich auch einen äquivalenten regulären Ausdruck angeben.
Hast Du mal versucht einen Automaten dazu zu konsturieren?
Das könnte Dir helfen. Und dann schaust Du mal, welche Zeichenfolgen generiert werden können (falls DU nicht weißt, wie man so einen DFA zu einem regulären Ausdruck umformt).
Soweit sind wir noch nicht im Stoff, haben das Thema erst gestern begonnen, ich kann also mit Automaten noch nichts anfangen.
Und hast DU mal versucht mögliche Produktionen hinzuschreiben?
S->aA->aaS->aaaA->aaaaS ...wenn ich also vielfache von 2 für a habe, dann wird S quasi rechts weitergeschoben.
S->aA->aL (L=Lambda) fin.
S->aA->aaS->aaaA->aaaL
Für b läuft das genauso bei c gilt:
S->cS->ccS->cccS ....
-----
Ich kann also mit aa, bb und c das S rechts vor dem Wort 'herschieben' und kann dies kein Mal oder beliebige oft wiederholen. wie würde man also diese 3 Alternativen inklusive der Wiederholungen regulär aufschreiben? (Tip: Kleen'scher Abschluß)
Bis jetzt habe ich mich im Kreis gedreht, wenn ich also jetzt immernoch rechts ein S stehen habe, dann kann ich aus (.......)S nur terminieren, wenn ich ein a oder ein b produziere und dann A oder B (nicht-Terminal) in das Terminal Lambda überführe. wie sieht das also als regulärer Ausdruck aus?
Und nun fügst Du es zusammen und hast Deine Lösung.
Ok, meinst du es vielleicht so hier:
L(G1)={x | x Element { aa, bb, c }^* } ?
Nein, denn das gibt nur die verschiedenen Zyklenalternativen wieder, DU hast den zweiten Abschnitt weggelassen - das erzeugt Dir alle Prefixwörter, die das S vor sich herschieben - jetzt mußt du nur noch terminieren, indem Du (...)S in (...)aA und dies in (...)aL überführst (oder eben die zweite Terminierungsalternative).
Komm schon, es ist wirklich nicht schwer - schreibe erstmal nur den regulären Ausdruck nieder.
L(G1)={xy | x Element { aa, bb, c }^* und y Element sum2 }
Ich habe zwar keine Ahnung warum aber könnte dies stimmen?
Okay, ich gebs auch, ich zerre Dich nicht weiter am Nasenring durch die Manege - Der reguläre Ausdruck wäre:
(aa|bb|c)*(a|b)
Den Rest mußt Du nun alleine schaffen.
Ok, verstehe es zwar überhaupt nicht, naja, danke dennoch
Was soll y Element sum2 bedeuten?
Ergibt so für mich leider keinen Sinn.
Nur am Rande, weil ich es vorher nicht gesehen hatte: Die Produktionen sind mit P_1 bezeichnet, während oben bei der Grammatik ein P_6 steht. Fehlt hier eventuell etwas für den Gesamtzusammenhang?
Übrigens steht da auch nirgends, was Lambda sein soll, daher habe ich diesbezüglich eien Annahme gemacht.
Du musst einen regulären Ausdruck finden, indem du überlegst, wie die Ableitungen dein Wort verändern. Überleg dir auch bei welchen Variablen dein Wort enden kann. Bei S z.B nicht, da S weder auf ein Kombination aus reinen Buchstaben abzubilden ist noch auf das leere Wort(hier Lambda). A und B aber schon. Wenn man sich die Variablen anschaut, dann sieht man, dass ein c nur durch S entstehen kann, dass und da A und B zu irgendwas zusammen mit S ableitbar sind, und man bei S soviele cs wie möglich machen kann oder eben keins, weisst du das dein Wort schonmal so aussieht: c* irgendwas c* irgendwas .... c* .
Nun sieht man noch, dass wenn man S zu aA ableitet, dies im Endeffekt zu aaS wid und bei S zu bB zu bbS. Du hängst also in jedem Schritt aa oder bb an. Außer im letzen Schritt, dort (a|b).
Alles miteinander müsste dies ergeben:
((c)*(aa|bb))* (a|b). Auf Deutsch: Du hast irgendeine Anzahl cs, dann aa oder bb . Dies wiederholst du wie oft du Lust hast, ABER am Ende muss a oder b noch angefügt werden.
Die Sprache ist die Menge aller Wörter die du ableiten kannst.
Die würde dann aber immer anders aussehen?
Könntest du mir einmal zeigen wie es gehen würde?
Danke für die Antwort, könntest du es mir vlt hier einmal beispielhaft vorrechen, ggf auch an einem anderen Beispiel? Ich muss das einmal sehen , leider gibt es nirgends eine ordentliche Erklärung (schrittweise) dazu, immer wird die Lösung sofort angegeben.