+1 Daumen
2,4k Aufrufe

Bitte um Hilfe bei den folgenden Aufgaben:

Prüfen Sie, ob folgende Sprachen über dem Alphabet ∑={a,b,c} kontextfrei sind. Falls die
Sprache nicht kontextfrei ist, beweisen Sie dies mit Hilfe des Pumping-Lemmas für kontextfreie
Sprachen. Falls die Sprache kontextfrei ist, geben Sie eine CFG an, welche die Sprache erzeugt.


a) L1={anbma2n  |  n≥1, m≥1}
b) L2={w∈∑* |  |w|a=|w|b,  |w|c = 2*|w|a}


VIELEN DANK!
Avatar von

1 Antwort

+1 Daumen

a) Eine CFG die die Sprache L1 erzeugt ist die folgende: 

$$S \rightarrow aAaa \\ A \rightarrow aAaa \mid B \\ B \rightarrow bB \mid b$$


Hast du eine Idee für b? Gibt es eine CFG die die Sprache L2 erzeugt?

Avatar von

Vielen Dank!

Ich habs versucht, aber keine Sprache gefunden.

Wenn es keine gibt, woe wird es mit dem PLemma widerlegt?

Ich werde mich sehr über deine Antwort freuen!


Vielen Dank. Es gibt doch noch nette Mitglieder im Forum

Wir behaupten dass L2 Kontextfrei ist. Also gilt das Pumping-Lemma. Sei n die Pumping Länge.

Sei s = an bn c2n .

Wir haben dass |s| = 4n >n and s is in L2.

Vom Pumping-Lemma haben wir folgendes:

∃ u,v,w,x,y sodass s=uvwxy, |vwx| ≤ n, |vx| ≥ 1 und uvwxy ∈ L ∀ i ≥ 0.

Da |vwx| ≤ n, gibt es die folgende Fälle:

  1. vwx enthält nur a
  2. vwx enthält nur b
  3. vwx enthält nur c
  4. vwx enthält a und b
  5. vwx enthält b und c
Siehst du dass es im jeden Fall mindestens ein i gibt sodass uvi wxi y ∉ L ? 


Ich verstehe zwei Sachen leider nicht :-(

1.:

Wieso ist |s|=4n?


2.:

Warum ist in jedem Fall u vi w xi y nicht Element L?


VIELEN DANK !! :-)

1. |s|=|an bn c2n |=|an | +|bn |+ |c2n | =n+n+2n=4n

(mit |a| meine ich die Länge von a,  an ist das Wort aa...aaa (n mal))


2. Fall 1:

vwx enthält nur a.

Für i=0 haben wir dass uv0 wx0 y=uwy weniger a als b enthält. also gilt dass uv0 wx0 y ∉ L.

So machst du das auch für die andere 4 Fälle.

Für i=1 hat man dann a und b oder b und c für vwx. Also immer noch weniger a als b? Stimmts?

Über welchen Fall sprichst du?

Ein anderes Problem?

Stell deine Frage