Pumping-Lemma, Beweis, kontextfrei

Question

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) L₁={aⁿb^ma²ⁿ  |  n≥1, m≥1}
b) L₂={w∈∑^* |  |w|_a=|w|_b,  |w|_c = 2*|w|_a}

VIELEN DANK!

Answer 1

a) Eine CFG die die Sprache L₁ 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 L₂ erzeugt?

Comments

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 L₂ Kontextfrei ist. Also gilt das Pumping-Lemma. Sei n die Pumping Länge.

Sei s = aⁿ bⁿ c²ⁿ .

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

Vom Pumping-Lemma haben wir folgendes:

∃ u,v,w,x,y sodass s=uvwxy, |vwx| ≤ n, |vx| ≥ 1 und uvⁱ wxⁱ y ∈ 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 uvⁱ wxⁱ y ∉ L ? 

---

Ich verstehe zwei Sachen leider nicht :-(

1.:

Wieso ist |s|=4n?

2.:

Warum ist in jedem Fall u v^i w x^i y nicht Element L?

VIELEN DANK !! :-)

---

1. |s|=|aⁿ bⁿ c²ⁿ |=|aⁿ | +|bⁿ |+ |c²ⁿ | =n+n+2n=4n

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

2. Fall 1:

vwx enthält nur a.

Für i=0 haben wir dass uv⁰ wx⁰ y=uwy weniger a als b enthält. also gilt dass uv⁰ wx⁰ 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?