matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenFormale SprachenErfüllt Sprache das PL
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Formale Sprachen" - Erfüllt Sprache das PL
Erfüllt Sprache das PL < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Erfüllt Sprache das PL: kontextfrei
Status: (Frage) beantwortet Status 
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?

        
Bezug
Erfüllt Sprache das PL: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Erfüllt Sprache das PL: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
Erfüllt Sprache das PL: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                
Bezug
Erfüllt Sprache das PL: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                        
Bezug
Erfüllt Sprache das PL: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]