Grammatik, pre* usw. < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:51 Di 04.08.2009 | | Autor: | diecky |
| Aufgabe | Gegeben sei die Grammatik G mit
S -> AB | ASA
A -> aAB | a
B -> bSa | b
1. Aufgabe: Enthält L ein Wort aus L(G)?
2. Aufgabe: Wie lautet der reguläre Ausdruck für pre*(L) [mm] \cap [/mm] {a,b}* ?
3. Aufgabe: Gibt es eine Satzform [mm] \alpha, \beta [/mm] und [mm] \gamma, [/mm] sodass [mm] \gamma \in [/mm] L und [mm] \alpha [/mm] aa [mm] \beta [/mm] =>* [mm] \gamma [/mm] ? |
Hallo zusammen,
Ich würde gerne wissen ob meine Ideen richtig sind, bei der letzten Aufgabe bräuchte ich noch Hilfe, weil ich da nicht weiß wie es funktioniert.
Zur 1.Aufgabe:
Dort habe ich durch Ableitung gezeigt, dass sich z.B. das Wort abaabaaba erzeugen lässt und zwar so:
S => AB => aB => abSa => abASAa => abaSAa => abaABAa => abaaBAa => abaabAa => abaabaABa => abaabaaBa => abaabaaba
Zur 2.Aufgabe:
Die finde ich bereits etwas seltsam, denn {a,b}* ist ja als regulärer Ausdruck geschrieben einfach (a+b)*, was im Grunde genommen alles enthält, was man aus a und b erzeugen kann (plus Epsilon). Weshalb mach ich dann so einen Unfug (bzw. soll ich machen) , denn rein gedanklich ist doch schon klar, dass dabei nur wieder pre*(L) rauskommen kann, denn wenn ich eine Sprache mit allem schneide, was es sozusagen gibt, kann auch nur wieder die Sprache rauskommen - oder seh ich das falsch?
Nichts desto trotz habe ich es einfach mal versucht und pre*(L) aufgemalt,
also pre*((aba*)).
Was ich hier jedoch auch komisch finde ist, dass ich nicht mit einem S vom Anfangs- in den Endzustand gelange nach meiner Konstruktion und demnach dürfte ja kein Wort aus L erzeugbar sein, was ich aber bereits schon in Aufgabe 1 widerlegt habe.
Hmm...kann mir da jemand helfen?
Ansonsten hätte ich noch für den Schnitt einen zweiten Automaten (für (a+b)*) konstruiert, der ja ganz einfach ist und dann mittels Produktautomat den Schnitt gebildet - raus kommt aber wieder pre*(L)?!
Sollte das doch richtig sein (was ich nicht glaube), kann man dann ja den r.A. einfach erzeugen.
Zur 3.Aufgabe: Hier bin ich leider völlig überfragt. Was die Aufgabe soll ist mir schon klar: ich soll wohl irgendwelche Nonterminale finden, mit denen sich [mm] \alpha [/mm] aa [mm] \beta [/mm] zu irgendeinem Wort aus L (z.B. abaaba) ableiten lässt. Wie kann ich da mit der pre*-Methode vorgehen?
Vielen Dank für eure Hilfe/Hinweise, wie auch immer!!!!!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Mi 12.08.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
