Erfüllt Sprache das PL < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:55 Do 23.05.2013 | | Autor: | bandchef |
| Aufgabe | | Zeigen Sie, dass die Sprache [mm] $L=\{a^i b^j c^j d^j | i, j \in \mathbb N\} \cup \{b^i c^j d^k \in \mathbb N\}$ [/mm] die Aussage des PL für kontextfreie Sprachen erfüllt. |
Hi Leute!
Ich hab zur Lösung der Aufgabe, die Sprache L in zwei kleinere Sprachen [mm] $L_2$ [/mm] und [mm] $L_3$ [/mm] zerlegt:
[mm] $L=\underbrace{\{a^i b^j c^j d^j | i, j \in \mathbb N\}}_{=L_2} \cup \underbrace{\{b^i c^j d^k \in \mathbb N\}}_{=L_3}$
[/mm]
Da ich für beide Teilsprachen jeweils eine kontextfreie Grammatik [mm] $G_2$ [/mm] und [mm] $G_3$ [/mm] angeben kann erfüllt die gesamte Sprache $L$ wohl das PL, da die Vereinigung bei kontextfreien Sprachen ja abgeschlossen ist.
Die beiden Grammatiken lauten so:
[mm] $G_2=(V, \Sigma, [/mm] P, S)$, [mm] $V=\{S,B,C,D\}$, $\Sigma=\{b,c,d\}$, $P=\{S \to \epsilon, S \to BCD, B \to BB, C \to CC, D \to DD, B \to b, C \to c, D \to d\}$
[/mm]
[mm] $G_3=(V, \Sigma, [/mm] P, S)$, [mm] $V=\{S,A,B,C,D\}$, $\Sigma=\{a,b,c,d\}$, $P=\{S \to \epsilon, S \to AB, A \to AA, A \to a, B \to b, C \to c, D \to d, B \to BB, B \to BBC, C \to CCD, D \to DD\}$
[/mm]
Kann ich da so argumentieren?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:19 Sa 25.05.2013 | | Autor: | tobit09 |
Hallo bandchef,
> Zeigen Sie, dass die Sprache [mm]L=\{a^i b^j c^j d^j | i, j \in \mathbb N\} \cup \{b^i c^j d^k \in \mathbb N\}[/mm]
> die Aussage des PL für kontextfreie Sprachen erfüllt.
Sicherlich soll es hinten [mm] $\{b^ic^jd^k\;|\;i,j,k\in\IN\}$ [/mm] heißen.
> Ich hab zur Lösung der Aufgabe, die Sprache L in zwei
> kleinere Sprachen [mm]L_2[/mm] und [mm]L_3[/mm] zerlegt:
>
> [mm]L=\underbrace{\{a^i b^j c^j d^j | i, j \in \mathbb N\}}_{=L_2} \cup \underbrace{\{b^i c^j d^k \in \mathbb N\}}_{=L_3}[/mm]
>
> Da ich für beide Teilsprachen jeweils eine kontextfreie
> Grammatik [mm]G_2[/mm] und [mm]G_3[/mm] angeben kann erfüllt die gesamte
> Sprache [mm]L[/mm] wohl das PL, da die Vereinigung bei kontextfreien
> Sprachen ja abgeschlossen ist.
Die Argumentation wäre korrekt, wenn du tatsächlich kontextfreie Grammatiken für [mm] $L_2$ [/mm] und [mm] $L_3$ [/mm] angeben könntest. Tatsächlich ist aber [mm] $L_2$ [/mm] gar nicht kontextfrei.
Ich gehe im Folgenden davon aus, dass du [mm] $G_2$ [/mm] und [mm] $G_3$ [/mm] vertauscht hast.
> Die beiden Grammatiken lauten so:
>
> [mm]G_2=(V, \Sigma, P, S)[/mm], [mm]V=\{S,B,C,D\}[/mm], [mm]\Sigma=\{b,c,d\}[/mm],
> [mm]P=\{S \to \epsilon, S \to BCD, B \to BB, C \to CC, D \to DD, B \to b, C \to c, D \to d\}[/mm]
Das ist eine korrekte kontextfreie Grammatik für [mm] $L_3$.
[/mm]
> [mm]G_3=(V, \Sigma, P, S)[/mm], [mm]V=\{S,A,B,C,D\}[/mm], [mm]\Sigma=\{a,b,c,d\}[/mm],
> [mm]P=\{S \to \epsilon, S \to AB, A \to AA, A \to a, B \to b, C \to c, D \to d, B \to BB, B \to BBC, C \to CCD, D \to DD\}[/mm]
Das leere Wort liegt nicht in [mm] $L_2$. [/mm] Also passt die Regel [mm] $S\to\epsilon$ [/mm] nicht. Das lässt sich leicht beheben.
Deine Grammatik vermag nicht sicherzustellen, dass die Anzahlen der b's, c's und d's übereinstimmen.
Sie stellt außerdem weder sicher, dass überhaupt c's und d's vorkommen, noch dass die c's und d's ausschließlich an den richtigen Stellen kommen.
Zeige, dass die Aussage aus dem Pumping Lemma mit $n=1$ erfüllt ist!
Sei also [mm] $z\in [/mm] L$ (mit [mm] $|z|\ge1$).
[/mm]
Unterscheide die Fälle [mm] $z\in L_2$ [/mm] (also [mm] $z=a^ib^jc^jd^j$ [/mm] für gewisse [mm] $i,j\in\IN$) [/mm] und [mm] $z\in L_3$ [/mm] (also [mm] $z=b^ic^jd^k$ [/mm] für gewisse [mm] $i,j,k\in\IN$). [/mm] Gib jeweils eine Zerlegung von $z$ an, die den im PL genannten Bedingungen genügt!
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:52 Sa 25.05.2013 | | Autor: | bandchef |
> Sicherlich soll es hinten [mm] $\{b^ic^jd^k\;|\;i,j,k\in\IN\}$ [/mm] heißen.
Du hast Recht. Ich hab das vergessen einzutippen. Auf meinem Blatt steht das hier auch richtig so.
> Ich gehe im Folgenden davon aus, dass du [mm] $G_2$ [/mm] und [mm] $G_3$ [/mm] vertauscht hast.
Auch wieder richtig. Die korrekte kontextfreie Grammatik beschreibt die Sprache [mm] $L_3$. [/mm] Auch das steht hier eigentlich so auf meinem Blatt...
> Das leere Wort liegt nicht in [mm] $L_2$. [/mm] Also passt die Regel [mm] $S\to\epsilon$ [/mm] nicht. Das lässt sich leicht beheben.
> Deine Grammatik vermag nicht sicherzustellen, dass die Anzahlen der b's, c's und d's übereinstimmen.
> Sie stellt außerdem weder sicher, dass überhaupt c's und d's vorkommen, noch dass die c's und d's ausschließlich an den richtigen Stellen kommen.
Dann kann man also GAR KEINE Grammatik für [mm] $L_2$ [/mm] angeben, ja?
> Zeige, dass die Aussage aus dem Pumping Lemma mit $n=1$ erfüllt ist!
>Sei also [mm] $z\in [/mm] L$ (mit [mm] $|z|\ge1$). [/mm]
> Unterscheide die Fälle [mm] $z\in L_2$ [/mm] (also [mm] $z=a^ib^jc^jd^j$ [/mm] für gewisse [mm] $i,j\in\IN$) [/mm] und [mm] $z\in L_3$ [/mm] (also [mm] $z=b^ic^jd^k$ [/mm] für gewisse [mm] $i,j,k\in\IN$). [/mm] Gib jeweils eine Zerlegung von $z$ an, die den im PL genannten Bedingungen genügt!
Ich soll hier also nun das PL für beide Teilsprachen machen? Reicht es nicht, wenn ich das PL nur für die noch nicht als kontextfrei belegete Sprache [mm] $L_2$ [/mm] mache? Für [mm] $L_3$ [/mm] hab ich ja schon gezeigt, dass sie kontextfrei ist, da ich ja eine korrekte Grammatik angeben konnte! Warum muss ich dann das PL auch noch für [mm] $L_3$ [/mm] machen?
Wenn ich nun das PL für [mm] $L_2$ [/mm] mache, will ich wieder einen Widerspruchsbeweis durchführen, in dem ich behaupte, dass sie nicht kontextfrei ist im Beweis aber dann annehme, dass sie kontextfrei wäre, dass aber dann widerlege, richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:35 Sa 25.05.2013 | | Autor: | tobit09 |
> Dann kann man also GAR KEINE Grammatik für [mm]L_2[/mm] angeben,
> ja?
Gar keine kontextfreie.
> > Zeige, dass die Aussage aus dem Pumping Lemma mit [mm]n=1[/mm]
> erfüllt ist!
>
> > Sei also [mm]z\in L[/mm] (mit [mm]|z|\ge1[/mm]).
>
> > Unterscheide die Fälle [mm]z\in L_2[/mm] (also [mm]z=a^ib^jc^jd^j[/mm] für
> gewisse [mm]i,j\in\IN[/mm]) und [mm]z\in L_3[/mm] (also [mm]z=b^ic^jd^k[/mm] für
> gewisse [mm]i,j,k\in\IN[/mm]). Gib jeweils eine Zerlegung von [mm]z[/mm] an,
> die den im PL genannten Bedingungen genügt!
>
> Ich soll hier also nun das PL für beide Teilsprachen
> machen?
Nein. Du sollst zeigen, dass die Bedingung aus dem Pumping Lemma für die gesamte Sprache $L$ gilt.
> Reicht es nicht, wenn ich das PL nur für die noch
> nicht als kontextfrei belegete Sprache [mm]L_2[/mm] mache? Für [mm]L_3[/mm]
> hab ich ja schon gezeigt, dass sie kontextfrei ist, da ich
> ja eine korrekte Grammatik angeben konnte! Warum muss ich
> dann das PL auch noch für [mm]L_3[/mm] machen?
Du könntest theoretisch separat zeigen, dass [mm] $L_2$ [/mm] und [mm] $L_3$ [/mm] dem Pumping Lemma genügen. Dann müsstest du aber noch zeigen, dass die Vereinigung zweier dem Pumping Lemma genügender Sprachen wieder dem Pumping Lemma genügt. Das erscheint mir komplizierter (wenn auch durchaus eleganter) als der von mir vorgeschlagene direkte Weg.
> Wenn ich nun das PL für [mm]L_2[/mm] mache, will ich wieder einen
> Widerspruchsbeweis durchführen, in dem ich behaupte, dass
> sie nicht kontextfrei ist im Beweis aber dann annehme, dass
> sie kontextfrei wäre, dass aber dann widerlege, richtig?
Es geht hier nicht um Kontextfreiheit, sondern um Gültigkeit der "es existiert ein [mm] $n\in\IN$, [/mm] so dass für alle [mm] $z\in [/mm] L$ mit [mm] $|z|\ge [/mm] n$..."-Bedingung.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:50 Sa 25.05.2013 | | Autor: | bandchef |
> Nein. Du sollst zeigen, dass die Bedingung aus dem Pumping Lemma für die gesamte Sprache $L$ gilt.
Ah, verstehe...
> Du könntest theoretisch separat zeigen, dass [mm] $L_2$ [/mm] und [mm] $L_3$ [/mm] dem Pumping Lemma genügen. Dann müsstest du aber noch zeigen, dass die Vereinigung zweier dem Pumping Lemma genügender Sprachen wieder dem Pumping Lemma genügt. Das erscheint mir komplizierter (wenn auch durchaus eleganter) als der von mir vorgeschlagene direkte Weg.
Ok. Dann mach ich nun einen PL-Beweis den ich wohl in 2 Fälle unterscheiden muss:
Behauptung: L ist kontextfrei.
Sei [mm]L[/mm] eine kontextfreie Sprache, dann gibt es eine
Konstante [mm]n \in \mathbb N[/mm], so dass sich jedes [mm]z \in L[/mm] mit
[mm]|z|\geq n[/mm], so als z=uvwxy schreiben lässt, dass [mm]|vwx|\leq n[/mm],
[mm]|vx|\geq 1[/mm] und [mm]u v^i w x^i y \in L[/mm] für alle [mm]i \geq 0[/mm]
gilt:
1.Fall:
wähle: [mm] $a^i b^j c^j d^j$, [/mm] $|z|=i+j+j+j=i+3j$, [mm] $i,j\in \mathbb [/mm] N$
setze: [mm] $u=\epsilon, [/mm] v=a, [mm] w=a^{i-1}, [/mm] x=b, [mm] y=b^{j-1} c^j d^j$
[/mm]
[mm] $\Rightarrow [/mm] uv^lwx^ly = [mm] a^l a^{i-1} b^l b^{j-1} c^j d^j \in [/mm] L$ gilt für $l=1$
oder für Fall 1 diese Aufteilung: [mm] $\Rightarrow [/mm] uv^lwx^ly = [mm] a^l a^{i-2l} a^l b^j c^j d^j \in [/mm] L$ gilt für alle $l [mm] \geq [/mm] 0$
Welche der beiden Arten würdest du sagen sind richtig, falls überhaupt eine richtig ist 
Nun noch der 2. Fall:
wähle: [mm] $b^ic^jd^k \in [/mm] L, i+j+k [mm] \geq [/mm] n$
[mm] $\Rightarrow [/mm] = uv^lwx^ly = [mm] b^l b^{i-2} b^l c^j d^k \in [/mm] L, [mm] \forall [/mm] l [mm] \geq [/mm] 0$
Aber welchen Schluss ziehe ich nun für die Sprache L daraus? Ich hab ja nun belegt, dass es für L ein n gibt, für das das PL gilt... Irgendwie hab ich das noch nicht ganz kapiert... Vor allem ist ja nun L kontextfrei obwohl die Teilsprache [mm] $L_2$ [/mm] nicht kontextfrei ist?!?!? Erzeugt also die Vereinigung einer nicht kontextfreien Sprache (hier [mm] $L_2$) [/mm] mit einer kontextfreien Sprachen (hier [mm] $L_3$) [/mm] die dann dennoch kontextfreie Sprache L?
> Ich gehe im Folgenden davon aus, dass du [mm] $G_2$ [/mm] und [mm] $G_3$ [/mm] vertauscht hast.
> Die beiden Grammatiken lauten so:
>
> [mm]G_2=(V, \Sigma, P, S)[/mm], [mm]V=\{S,B,C,D\}[/mm], [mm]\Sigma=\{b,c,d\}[/mm],
> [mm]P=\{S \to \epsilon, S \to BCD, B \to BB, C \to CC, D \to DD, B \to b, C \to c, D \to d\}[/mm]
> Das ist eine korrekte kontextfreie Grammatik für [mm] $L_3$.
[/mm]
Warum ist in [mm] $L_3$ ($G_3$) [/mm] das leere Wort, also die Ableitung $S [mm] \to \epsilon$, [/mm] zugelassen und in [mm] $L_2$ ($G_2$) [/mm] ist es nicht zugelassen? Ich sehe gerade den Grund dafür nicht?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:01 Mo 27.05.2013 | | Autor: | tobit09 |
> Behauptung: L ist kontextfrei.
Wenn du das zeigen könntest, hättest du in der Tat gewonnen, denn dann würde dir das PL liefern, dass die Bedingung aus dem PL für L erfüllt ist.
Das wird dir aber nicht gelingen, denn L ist nicht kontextfrei.
Wie ich weiter unten sehe, versuchst du aber auch gar nicht, die Kontextfreiheit von L zu zeigen.
> Sei [mm]L[/mm] eine kontextfreie Sprache, dann gibt es eine
> Konstante [mm]n \in \mathbb N[/mm], so dass sich jedes [mm]z \in L[/mm] mit
> [mm]|z|\geq n[/mm], so als z=uvwxy schreiben lässt, dass [mm]|vwx|\leq n[/mm],
> [mm]|vx|\geq 1[/mm] und [mm]u v^i w x^i y \in L[/mm] für alle [mm]i \geq 0[/mm]
> gilt:
Behauptung: Für $n:=1$ gilt, dass sich jedes [mm]z \in L[/mm] mit [mm]|z|\geq n[/mm], so als z=uvwxy schreiben lässt, dass [mm]|vwx|\leq n[/mm], [mm]|vx|\geq 1[/mm] und [mm]u v^i w x^i y \in L[/mm] für alle [mm]i \geq 0[/mm] gilt.
> 1.Fall:
>
> wähle: [mm]a^i b^j c^j d^j[/mm], [mm]|z|=i+j+j+j=i+3j[/mm], [mm]i,j\in \mathbb N[/mm]
>
> setze: [mm]u=\epsilon, v=a, w=a^{i-1}, x=b, y=b^{j-1} c^j d^j[/mm]
>
> [mm]\Rightarrow uv^lwx^ly = a^l a^{i-1} b^l b^{j-1} c^j d^j \in L[/mm]
> gilt für [mm]l=1[/mm]
Wir suchen jedoch eine Aufteilung, so dass dies für ALLE [mm] $l\in\IN_0$ [/mm] gilt.
> oder für Fall 1 diese Aufteilung: [mm]\Rightarrow uv^lwx^ly = a^l a^{i-2l} a^l b^j c^j d^j \in L[/mm]
> gilt für alle [mm]l \geq 0[/mm]
Gib in Abhängigkeit von i und j konkret u,v,w,x und y an.
Die Idee, den Teil uvwx in die a's zu legen, ist völlig korrekt.
Z.B. für i=1 musst du dazu drei der vier Teile u,v,w und x als leeres Wort wählen.
Um zu einer allgemeinen Lösung zu kommen, könntest du z.B. ebenfalls uvwx so wählen, dass uvwx=a, also in u,v,w und x sozusagen nur das erste a drinsteckt. Dann musst du [mm] y=a^{i-1}b^jc^jd^j [/mm] wählen.
> Nun noch der 2. Fall:
>
> wähle: [mm]b^ic^jd^k \in L, i+j+k \geq n[/mm]
>
> [mm]\Rightarrow = uv^lwx^ly = b^l b^{i-2} b^l c^j d^k \in L, \forall l \geq 0[/mm]
Hier gilt Analoges.
> Aber welchen Schluss ziehe ich nun für die Sprache L
> daraus? Ich hab ja nun belegt, dass es für L ein n gibt,
> für das das PL gilt...
Genau das war die Aufgabe. Die Sprache L ist ein Beispiel für eine nicht kontextfreie Sprache, für die dennoch die Bedingung aus dem PL gilt.
> Irgendwie hab ich das noch nicht
> ganz kapiert... Vor allem ist ja nun L kontextfrei obwohl
> die Teilsprache [mm]L_2[/mm] nicht kontextfrei ist?!?!?
Nein, L ist nicht kontextfrei.
> Erzeugt also
> die Vereinigung einer nicht kontextfreien Sprache (hier
> [mm]L_2[/mm]) mit einer kontextfreien Sprachen (hier [mm]L_3[/mm]) die dann
> dennoch kontextfreie Sprache L?
Das lässt sich nicht allgemein sagen. Die Vereinigung einer kontextfreien mit einer nicht kontextfreien Sprache kann sowohl kontextfrei als auch nicht kontextfrei sein.
> > Ich gehe im Folgenden davon aus, dass du [mm]G_2[/mm] und [mm]G_3[/mm]
> vertauscht hast.
> > Die beiden Grammatiken lauten so:
> >
> > [mm]G_2=(V, \Sigma, P, S)[/mm], [mm]V=\{S,B,C,D\}[/mm], [mm]\Sigma=\{b,c,d\}[/mm],
> > [mm]P=\{S \to \epsilon, S \to BCD, B \to BB, C \to CC, D \to DD, B \to b, C \to c, D \to d\}[/mm]
> > Das ist eine korrekte kontextfreie Grammatik für [mm]L_3[/mm].
>
> Warum ist in [mm]L_3[/mm] ([mm]G_3[/mm]) das leere Wort, also die Ableitung [mm]S \to \epsilon[/mm],
> zugelassen und in [mm]L_2[/mm] ([mm]G_2[/mm]) ist es nicht zugelassen? Ich
> sehe gerade den Grund dafür nicht?
Dein Einwand ist völlig berechtigt: Ich habe bei der Grammatik für [mm] $L_3$ [/mm] vergessen einzuwenden, dass sie ja auch das leere Wort produziert, was nicht in [mm] $L_3$ [/mm] liegt. Du musst also auch bei dieser Grammatik die Regel [mm] $S\to\epsilon$ [/mm] entfernen.
|
|
|
|
