Zeigen Sie, dass die Sprache L kontextfrei ist, indem Sie eine kontextfreie Grammatik G mit L(G) = L angeben.

Question

Frage:

Sei die folgende Sprache über dem Alphabet Σ = {a,b,c} gegeben:

L = {a^i b^j c^k a^l b^m c^i | i, j, k, l, m ∈ ℕ, j ≤ k, l > m}

Zeigen Sie, dass die Sprache L kontextfrei ist, indem Sie eine kontextfreie Grammatik G mit L(G) = L angeben.

Ansatz:

Eine Grammatik G = (V,T,R,S) heißt kontextfrei, gdw. ∀ (P -> Q) ∈ R (P ∈ V und Q ∈ (V ∪ T)*)

• Links eine einzelne Variable

• Die Prämisse macht keine Aussage, was der Kontext dieser Variablen ist

• Rechts steht etwas Belibiges

Wie gehe ich hier vor? Ich habe zwar eine Musterlösung, ich finde es aber extrem schwer, selbst darauf zu kommen.

Wie muss ich denn denken, um es zu lösen.

j ≤ k, l > m

Was leite ich hieraus ab? Wie fange ich an? Gibt das einen Hinweis darauf, mit welcher Regel ich zuerst anfangen sollte?

Liebe Grüße

Comments

Also,

man könnte mit dieser Sprache folgendes Wort erzeugen:

w1 = aabbcccaabc

Also habe ich versucht, Regeln für dieses Wort zu finden:

A -> aA | aB | B | aC,

B -> bB | bC,

C -> cC | caB | ε }

Wäre das so korrekt?

---

Die Musterlösung lautet:

S -> aSc | KL,

K -> bKc | Kc | ε,

L -> aLb | aL | a}

Ich hab absolut keine Ahnung, wie man da vorgehen muss, um von selbst auf diese Gedanken zu kommen.

---

Also,man könnte mit dieser Sprache folgendes Wort erzeugen: w1 = aabbcccaabc

Das stimmt nicht ganz, die Anzahl an a's am Anfang muss gleich der Anzahl der c's am Ende sein (a^{i}...c^{i} wie es in der Definition der Sprache steht).

---

Ups, stimmt. Dann noch ein c am ende.

Answer 1

Nehmen wir zum Beispiel mal das Wort

x = aaaabccaabcccc und schauen uns an wie wir dieses mit der Grammatik aus der Musterlösung erzeugen können.

1. Erzeuge die 4 a's am Anfang und die 4 c's am Ende des Wortes. Dies geht über die Regel S -> aSc.

S -> aSc -> aaScc -> aaaSccc -> aaaaScccc

Mit der Regel S -> KL gehts dann weiter

2. Jetzt zur Erzeugung von b^{j}c^{k}:

Die Regel K -> bKc funktioniert wie die Regel S -> aSc

Mit der Regel K -> Kc kannst du dafür sorgen das du mehr c's als bist hast

Du kannst aber auch keine b's und c's haben, hier kommt die Regel K -> ε ins Spiel

Also zurück zu unserem Beispiel:

S -> aSc -> aaScc -> aaaSccc -> aaaaScccc

-> aaaaKLcccc -> aaaabKcLcccc -> aaaabKccLcccc

-> aaaabccLcccc

3. Nun zur Erzeugung von a^{l}b^{m} mit l <m

Hier musst du mindestens ein a mehr haben als b's.

Du kannst beispielsweise ein a erzeugen mit L -> a oder auch mehrere mit L -> aL oder du benutzt eben die Regel L -> aLb dann musst du aber irgendwann zwingend ein einzelnes a einbauen, sodass du mehr a's als b's bekommst.

Wieder zum Beispiel:

S -> aSc -> aaScc -> aaaSccc -> aaaaScccc

-> aaaaKLcccc -> aaaabKcLcccc -> aaaabKccLcccc

-> aaaabccLcccc -> aaaabccaLbcccc

-> aaaabccaabcccc

Hoffe das hilft dir weiter

Comments

Bei folgender Sprache:

L = {(ab)^i(ba)^j | 0 < i ≤ j}

habe ich mal folgendes Wort produziert:

w = abbaba

Und bin dann auf folgende Regelmenge gekommen:

{S -> aSa | bSb | bS | aS | ε }

Das wäre doch eine kontextfreie Grammatik, oder?

---

Die Musterlösung lautet: R = {S -> abSba | Sba | abba}

Wenn aber meine Annahme richtig ist, dass das Wort w = abbaba von der Sprache L akzeptierbar ist ,dann weiß ich nicht, wie man das Wort von der Regelmenge aus der Musterlösung ableiten könnte.

Denn: S -> abSba (die äußeren ab, ba), dann abSba -> abSbaba

Jetzt stört das S, also müsste man noch in der Regelmenge die Regel S -> ε ergänzen.

Habe ich recht?

---

Für die Sprache

L = {a^n w a^k | n,k ≥ 1, w ∈ {b,c}*, |w| ≤ k}

käme ich auf

R =

{

S -> aLa | aL | La,

L -> bL | cL | La | ε

}

Was sagt ihr dazu?