Welche Sprache erzeugt diese Grammatik |
09.12.2006, 15:46 | Auf diesen Beitrag antworten » | ||||
lego | Welche Sprache erzeugt diese Grammatik Hallo, habe hier eine Übungsaufgabe, mit der ich nicht ganz klar komme. Welche Sprache wird von der kontextfreien Grammatik S->aXa, S->bXa, X->aXa, x->bXa und x-># (leeres Wort) erzeugt. Ich hab mal ein weng ausprobiert, und denke es musste eine Sprache sein, bei der ein wort am anfang immer entweder beliebig viele a's oder b's hat, dann beliebigviele vom anderen Buchstaben, und das beliebig lange und alternierend hat und am Ende des Wortes, sind so viele a's, wie vorher a's und b's gemeinsam. also wenn ich mit a's Anfange, dann meine ich so L={a^m b^n a^o b^p...b^z a^(m+n+o+p+...+z), alle indizes >=1} und analog, wenn ich mit b's Anfange. aber 1. ist das ganze ein wenig "schwammig" und konfus, 2tens, bin ich mir nicht ganz sicher ob das stimmt, und 3. hätte ich gerne eine schönere Darstellung meiner Sprache als geschlossenen Anusdruck. Könnt ihr mir bitte helfen. |
||||
|
|||||
09.12.2006, 16:46 | Auf diesen Beitrag antworten » | ||||
Tobias | Erstmal das ganze etwas schöner aufgeschrieben: Jetzt sehen wir, dass durch jede Produktionsregel entweder zwei Terminale (a, b) oder keins hinzugefügt wird. Dadurch ergibt sich, dass jedes Wort gerade Länge hat. Wir können also schreiben: Ferner kannst du erkennen, dass rechts vom Nichtterminal immer nur ein "a" hinzugefügt wird. Daraus ergibt sich sofort: Links vom Nichtterminal hast du freie Wahl ob du beim Ableiten a oder b nimmst, also: Wir definieren die Sprache nun also korrekt indem wir formalisieren: Ein Wort der Sprache besteht aus zwei Teilwörtern derselben Länge. Das erste Teilwort ist aus Damit: Das Ganze lässt sich natürlich noch per Induktion beweisen. Aber ich denke das ist recht intuitiv klar. |
||||
09.12.2006, 17:26 | Auf diesen Beitrag antworten » | ||||
lego | oh, danke, das hat mir schonmal sehr geholfen, immerhin meinte ich das richtige, wenn ich mir deine lösung nun anschaue wie gehe ich da vor, wenn ich das induktiv beweisen soll, weiss nicht genau, wie der prof. das haben möchte, will dann nicht blöd dastehen, wenn ers bewiesen haben will. |
||||
09.12.2006, 21:36 | Auf diesen Beitrag antworten » | ||||
Asgard | Müsste es nicht eher lauten (also + statt *), da eine Epsilon-Produktion erst im zweiten Schritt möglich ist? Um dieses zu beweisen, musst Du |
||||
Anzeige | |||||
|
|||||
10.12.2006, 14:06 | Auf diesen Beitrag antworten » | ||||
Asgard | Meine Beweisidee wäre Folgende, wobei ich aber auf Induktion verzichten würde. In unserer Übung wurde gesagt, man könne es auch ausformuliert aufschreiben, aber ich weiß nicht, ob das auch wirklich ausreichend ist. Wäre schön, wenn jemand mit Ahnung dazu etwas sagen könnte. Natürlich wäre ein Beweis mittels Induktion schöner, aber ich habe immernoch keine Ahnung, wie dieser auszusehen hätte. |
||||
10.12.2006, 15:15 | Auf diesen Beitrag antworten » | ||||
Tobias | Also Asgard hat natürlich Recht: Es muss Ich unterbreite euch mal meinen Vorschlag für den Beweis. Anfang: Sei Es gibt nur die beiden Wörter Zu beiden Wörtern existiert eine Ableitung Hypothese: Sei Schluss: Wir müssen nur die Wörter Der umgekehrte Fall Der Anfang ist eine Ableitung mit 2 Schritten. Beide Wörter sind natürlich in L. Nun nehmen wir an, dass alle Wörter, die man aus maximal n Ableitungsschritten konstruieren kann, in L liegen. Alle diese Wörter haben einen Ableitungsstrang Dabei bedeutet Jetzt machen wir maximal n+1 Ableitungsschritte unter Verwendung der Hypothese: Wegen Somit haben wir bewiesen |
||||
10.12.2006, 16:57 | Auf diesen Beitrag antworten » | ||||
lego | oh, das war sehr ausführlich, danke schon mal, muss mal versuchen, das nachzuvollziehen, aber ich hätte mal eine kleine zwischenfrage, was ist der unterschied zwischen {...}^* und {...}^+ ? also * dachte ich, würde heißen, das freie monoid über {...}, aber + hab ich noch nicht gesehen |
||||
10.12.2006, 17:18 | Auf diesen Beitrag antworten » | ||||
Asgard | Es gilt z.B.: Mit dem Sternchen beschreibt man die Menge aller Wörter. Im Beispiel gilt also: Mit dem Plus wird die Menge aller nichtleeren Wörter beschrieben. Das Epsilon fällt also raus. Bei Deiner Aufgabe kann man sehen, dass aus S nicht das leere Wort gebildet werden kann. Um alle Nichtterminalzeichen zu eleminieren musst Du mindestens zwei Ableitungen ausführen, wobei Du Terminalzeichen erzeugst. Das gebildete Wort kann also nie leer sein. Der Beweis sieht gut aus, vielen Dank. Dürfte für meine Klausurvorbereitung sehr nützlich sein ![]() |
||||
10.12.2006, 17:54 | Auf diesen Beitrag antworten » | ||||
Tobias | Die positive Hülle ist nicht unbedingt die Menge der nichtleeren Wörter. Das gilt nur dann, wenn die Basismenge das leere Wort nicht enthält. Für alle Sprachen L mit |
||||
10.12.2006, 18:35 | Auf diesen Beitrag antworten » | ||||
Asgard | Entweder verstehe ich Dich falsch, oder in unserer Vorlesung wurde etwas anderes gelehrt. Für
Folgerung: Laut dieser Definition würde doch |
||||
10.12.2006, 18:48 | Auf diesen Beitrag antworten » | ||||
Tobias | Nein, nicht wenn das leere Wort schon in L drin ist. Mache dir das klar: Beweis: Wegen Seien M und N zwei Sprachen, dann ist das leere Wort in MN nur dann, wenn es sowohl in M als auch in N ist. Sei |
||||
10.12.2006, 19:29 | Auf diesen Beitrag antworten » | ||||
Asgard | Ist hier nicht ein Widerspruch?
Auf der einen Seite ist Auf der anderen Seite ist aber Auch steht im Buch "Theoretische Informatik - kurzgefasst" von Uwe Schöning Folgendes:
EDIT: Wie menschlich das Versagen! Mein Fehler liegt darin, dass alles was ich meine, auf Alphabete bezogen ist und nicht auf Sprachen. |
||||
10.12.2006, 19:41 | Auf diesen Beitrag antworten » | ||||
Tobias | Das ist kein Widerspruch, denn ich sagte es muss in mindestens einem L^i drin sein. Das schließt nicht aus, dass es in allen L^i drin ist. Ich nehme die Definition: Jetzt muss das leere Wort ja irgendwo hergekommen sein. Also laut erster naiver Annahme aus mindestens einer der Menge L^i. Das schließt weder aus, dass es in allen drin sein kann noch schließt es aus, dass es in einem L^j nicht drin ist. Dann kommt das nächste Argument... |
||||
10.12.2006, 21:15 | Auf diesen Beitrag antworten » | ||||
Asgard | Ich verstehe nur Folgendes nicht so ganz:
Wenn nun also |
||||
10.12.2006, 21:44 | Auf diesen Beitrag antworten » | ||||
Tobias | Das ist kein Denkfehler, das ist richtig. Nochmal mein Argument: Wenn M und N beliebige Mengen sind, dann kann man sagen: Das erweitern wir auf Wo siehst du nun einen Widerspruch? |
||||
10.12.2006, 22:11 | Auf diesen Beitrag antworten » | ||||
Asgard | Jetzt sehe ich ihn nicht mehr, aber Du veränderst auch gerade Deine Aussagen ![]()
Jetzt bin ich verwirrt ![]() Doch so langsam kommt die Erleuchtung auf simplem Wege: Aus |
||||
10.12.2006, 22:32 | Auf diesen Beitrag antworten » | ||||
Tobias | Ich glaube dich hat die Reihenfolge meines "Hilfssatzes" negativ beeinflusst. ![]() Meine Argumentationskette ist eigentlich: Voraussetzung: Leeres Wort ist in L^+ zu zeigen: Leeres Wort ist in L 1. Schritt: Es gibt es ein L^i, so dass leeres Wort in L^i ist 2.1 Schritt: Wenn i=1 ist alles gezeigt. 2.2 Schritt: Wenn i>1 ist leeres Wort in LL^(i-1). <-- hier meinen Satz über M und N anwenden |
||||
10.12.2006, 23:49 | Auf diesen Beitrag antworten » | ||||
Asgard | Jetzt ist das Licht endlich aufgegangen. Vielen Dank für Deine Geduld. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|