Informatiker Board | Theoretische Informatik | Welche Sprache erzeugt diese Grammatik

Informatiker Board » Themengebiete » Theoretische Informatik » Welche Sprache erzeugt diese Grammatik

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Seiten (2): [1] 2 nächste »

Welche Sprache erzeugt diese Grammatik

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

lego
Jungspund

Dabei seit: 19.11.2006
Beiträge: 11

Welche Sprache erzeugt diese Grammatik

Zitatantwort auf diesen Beitrag erstellen

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 15:46

Nehmen Sie lego in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Erstmal das ganze etwas schöner aufgeschrieben:

$[latex]S \to bXa \quad | \quad aXa[/latex]$
$[latex]X \to bXa \quad | \quad aXa \quad | \quad \epsilon[/latex]$

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:

$[latex]w = w_1w_2 \quad, \quad |w_1| = |w_2|[/latex]$

Ferner kannst du erkennen, dass rechts vom Nichtterminal immer nur ein "a" hinzugefügt wird. Daraus ergibt sich sofort:

$[latex]w_2 = a^n \quad , \quad n \in \mathbb{N}[/latex]$

Links vom Nichtterminal hast du freie Wahl ob du beim Ableiten a oder b nimmst, also:

$[latex]w_1 = (a+b)^n \quad , \quad n \in \mathbb{N}[/latex]$

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 $[latex]\{a,b\}^\ast[/latex]$ und das zweite aus $[latex]\{a\}^\ast[/latex]$ .

Damit:

$[latex]L = \big\{ w_1w_2 \; | \; w_1 \in \{a,b\}^\ast, \; w_2 \in \{a\}^\ast, \; |w_1| = |w_2| \big\}[/latex]$

Das Ganze lässt sich natürlich noch per Induktion beweisen. Aber ich denke das ist recht intuitiv klar.

09.12.2006 16:46

Nehmen Sie Tobias in Ihre Freundesliste auf

lego
Jungspund

Dabei seit: 19.11.2006
Beiträge: 11

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 17:26

Asgard
Jungspund

Dabei seit: 09.12.2006
Beiträge: 12

Müsste es nicht eher

$[latex]L=\{w_1w_2 \mid w_1\in \{a,b\}^{+}, w_2\in \{a,b\}^{+}, \mid w_1 \mid = \mid w_2 \mid \}[/latex]$

lauten (also + statt *), da eine Epsilon-Produktion erst im zweiten Schritt möglich ist?

Um dieses zu beweisen, musst Du [latex]L = L(G)[/latex]

zeigen. $[latex]L \subseteq L(G)[/latex]$ wird bei uns meist durch Induktion über die Wortlänge, $[latex]L(G) \subseteq L[/latex]$ durch Induktion über die Anzahl der Ableitungsschritte gezeigt. Wie dies im konkreten Fall aussehen könnte ist mir aber selbst noch schleierhaft.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Asgard: 09.12.2006 21:37.

09.12.2006 21:36

Nehmen Sie Asgard in Ihre Freundesliste auf

Asgard
Jungspund

Dabei seit: 09.12.2006
Beiträge: 12

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.

$[latex]L \subseteq L(G)[/latex]$ : Sei $[latex]w \in L[/latex]$ . Hier wäre zu zeigen, dass eine Ableitung $[latex]S \Rightarrow ^{*} w[/latex]$ existiert, um daraus zu folgern, dass $[latex]w \in L(G)[/latex]$ .

$[latex]L(G) \subseteq L[/latex]$ : Sei nun $[latex]w \in L(G)[/latex]$ . Dann gilt $[latex]S \Rightarrow ^{*} w[/latex]$ . Hier wäre dann der Wortaufbau zu beschreiben, wie es Tobias in seiner Herleitung der Sprache gemacht hat, um zu zeigen, dass $[latex]w \in L[/latex]$ .

Natürlich wäre ein Beweis mittels Induktion schöner, aber ich habe immernoch keine Ahnung, wie dieser auszusehen hätte.

10.12.2006 14:06

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Also Asgard hat natürlich Recht: Es muss $[latex]\{...\}^+[/latex]$ heißen, da die Wortlänge mindestens 2 ist.

Ich unterbreite euch mal meinen Vorschlag für den Beweis.

$[latex]L \subseteq L(G)[/latex]$ beweist man mit Induktion über die Wortlänge.

Anfang: Sei [latex]|w_1| = |w_2| = 1[/latex]

Es gibt nur die beiden Wörter $[latex]aa \in L[/latex]$ und $[latex]ba \in L[/latex]$ .
Zu beiden Wörtern existiert eine Ableitung
$[latex]S \Rightarrow aXa \Rightarrow a\epsilon a[/latex]$
$[latex]S \Rightarrow bXa \Rightarrow b\epsilon a[/latex]$

Hypothese: Sei $[latex]|w_1| = |w_2| = n \geq 2[/latex]$ und $[latex]w_1w_2 \in L[/latex]$ dann gibt es eine Ableitung $[latex]S \Rightarrow^\ast w_1Xw_2 \Rightarrow w_1\epsilon w_2[/latex]$

Schluss: Wir müssen nur die Wörter [latex]w_1aaw_2[/latex]

und

betrachten. Wir konstruieren die Ableitung, wobei $[latex]\Rightarrow^\ast[/latex]$ die Induktionshypothese benutzt:

$[latex]S \Rightarrow^\ast w_1Xw_2 \Rightarrow w_1aXaw_2 \Rightarrow w_1a\epsilon aw_2[/latex]$
$[latex]S \Rightarrow^\ast w_1Xw_2 \Rightarrow w_1bXaw_2 \Rightarrow w_1b\epsilon aw_2[/latex]$

Der umgekehrte Fall $[latex]L(G) \subseteq L[/latex]$ ist eine Induktion über die Anzahl der Ableitungsschritte.

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
$[latex]S \Rightarrow^{(n-1)} w_1Xw_2 \Rightarrow w_1\epsilon w_2[/latex]$
Dabei bedeutet $[latex]\Rightarrow^{(n-1)}[/latex]$ , dass maximal n-1 Ableitungsschritte gemacht wurden.

Jetzt machen wir maximal n+1 Ableitungsschritte unter Verwendung der Hypothese:

$[latex]S \Rightarrow^{(n-1)} w_1Xw_2 \Rightarrow w_1aXaw_2 \Rightarrow w_1a\epsilon a w_2[/latex]$

$[latex]S \Rightarrow^{(n-1)} w_1Xw_2 \Rightarrow w_1bXaw_2 \Rightarrow w_1b\epsilon a w_2[/latex]$

Wegen $[latex]w_1 \in \{a,b\}^+[/latex]$ sind natürlich auch $[latex]w_1a, w_1b \in \{a,b\}^+[/latex]$ . Wegen $[latex]w_2 \in \{a\}^+[/latex]$ natürlich auch $[latex]aw_2 \in \{a\}^+[/latex]$ .

Somit haben wir bewiesen [latex]L(G) = L[/latex]

10.12.2006 15:15

lego
Jungspund

Dabei seit: 19.11.2006
Beiträge: 11

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 16:57

Asgard
Jungspund

Dabei seit: 09.12.2006
Beiträge: 12

Es gilt z.B.: $[latex]\{a\}^{*}\{a\} = \{a\}^{+}[/latex]$

Mit dem Sternchen beschreibt man die Menge aller Wörter. Im Beispiel gilt also: $[latex]\{a\}^{*} = \{\epsilon, a, aa, aaa, aaaa, ....\}[/latex]$
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 Augenzwinkern

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Asgard: 10.12.2006 17:21.

10.12.2006 17:18

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

$[latex]L^\ast[/latex]$ für eine Sprache L ist die "Kleenesche Hülle". Diese ist natürlich ein freies Monoid bezüglich der Konkatenation weil $[latex]\epsilon \in L^\ast[/latex]$ das neutrale Element und L der Erzeuger des Monoids ist.

[latex]L^+[/latex]

ist die positive Hülle und nicht immer ein Monoid. Insbesondere gilt $[latex]\epsilon \in L^+ \iff \epsilon \in L[/latex]$

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 $[latex]\epsilon \in L[/latex]$ gilt $[latex]L^+ = L^\ast[/latex]$ .

10.12.2006 17:54

Asgard
Jungspund

Dabei seit: 09.12.2006
Beiträge: 12

Entweder verstehe ich Dich falsch, oder in unserer Vorlesung wurde etwas anderes gelehrt.

Für $[latex]L \subseteq {\sum}^{*}[/latex]$ sei

$[latex]L^{*} = \bigcup_{n\geq 0} L^{n} = \{w_1 ... w_n | n\geq 0, w_i \in L~fuer~i=1,...,n \}[/latex]$ der Kleene-Abschluss von L.
$[latex]L^{+} = \bigcup_{n\geq 1} L^{n} = \{w_1 ... w_n | n\geq 1, w_i \in L~fuer~i=1,...,n \} = LL^{*}[/latex]$

Folgerung: $[latex]L^{*} = L^{+} \cup L^{0} = L^{+} \cup \{\epsilon\}[/latex]$

Laut dieser Definition würde doch $[latex]L^{+}[/latex]$ das leere Wort bei einer Sprache ausschließen?!?

10.12.2006 18:35

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Nein, nicht wenn das leere Wort schon in L drin ist.

Mache dir das klar:

$[latex]\epsilon \in L \iff \epsilon \in L^+[/latex]$

Beweis:

$[latex] \Rightarrow [/latex]$
Wegen $[latex]\epsilon \in L[/latex]$ und $[latex]L \subseteq L^+[/latex]$ gilt auch $[latex]\epsilon \in L^+[/latex]$

$[latex] \Leftarrow [/latex]$
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 $[latex]\epsilon \in L^+[/latex]$ also in mindestens einem [latex]L^i[/latex]

für $[latex]i \geq 1[/latex]$ . Für i=1 ist der Fall klar. Für i>1 gilt:
$[latex]L^i = LL^{i-1}[/latex]$ und somit greift der Satz von oben.

10.12.2006 18:48

Asgard
Jungspund

Dabei seit: 09.12.2006
Beiträge: 12

Ist hier nicht ein Widerspruch?

Zitat:

Original von Tobias
$[latex] \Leftarrow [/latex]$
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 $[latex]\epsilon \in L^+[/latex]$ also in mindestens einem [latex]L^i[/latex]

für $[latex]i \geq 1[/latex]$ . Für i=1 ist der Fall klar. Für i>1 gilt:
$[latex]L^i = LL^{i-1}[/latex]$ und somit greift der Satz von oben.

Auf der einen Seite ist $[latex]\epsilon \in MN[/latex]$ wenn $[latex]\epsilon \in M[/latex]$ und $[latex]\epsilon \in N[/latex]$ .

Auf der anderen Seite ist aber $[latex]\epsilon \in L^{n}=LL^{n-1}[/latex]$ , wenn $[latex]\epsilon[/latex]$ in mindestens einem $[latex]L^{i}[/latex]$ für n>0 ist. Somit könnte doch durchaus ein $[latex]L^{i}~mit~\epsilon \not\in L^{i}[/latex]$ existieren.

Auch steht im Buch "Theoretische Informatik - kurzgefasst" von Uwe Schöning Folgendes:

Zitat:

Mit $[latex]{\sum}^{+}[/latex]$ bezeichnen wir $[latex]{\sum}^{*} - \{\epsilon\}[/latex]$

EDIT: Wie menschlich das Versagen! Mein Fehler liegt darin, dass alles was ich meine, auf Alphabete bezogen ist und nicht auf Sprachen.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Asgard: 10.12.2006 19:31.

10.12.2006 19:29

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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:

$[latex]L^+ = L L^1 L^2 L^3 \ldots L^i \ldots[/latex]$

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 19:41

Asgard
Jungspund

Dabei seit: 09.12.2006
Beiträge: 12

Ich verstehe nur Folgendes nicht so ganz:

Zitat:

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.

Wenn nun also $[latex]\epsilon \in L^{+}[/latex]$ , so müsste dann doch auch $[latex]\epsilon \in L^{i}[/latex]$ für jedes $[latex]i \geq 1[/latex]$ gelten, da doch laut obiger Aussage das leere Wort in der Konkatenation zweier Sprachen liegt, wenn es in beiden Sprachen vorhanden ist. Wo ist hier mein Denkfehler?

10.12.2006 21:15

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Das ist kein Denkfehler, das ist richtig.

Nochmal mein Argument:

Wenn M und N beliebige Mengen sind, dann kann man sagen: $[latex]x \in M \cup N \iff x \in M \vee x \in N[/latex]$

Das erweitern wir auf $[latex]L^+ = \bigcup_{n \geq 1} L^n[/latex]$ .

$[latex]x \in L^+ \iff x \in L^i \text{ fuer ein } i \geq 1[/latex]$

Wo siehst du nun einen Widerspruch?

10.12.2006 21:44

Seiten (2): [1] 2 nächste »

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Welche Sprache erzeugt diese Grammatik