Grammatik zu einer kontextfreien Sprache

Question

Es ist eine kontextfreie Grammatik also nur mit Regeln der Form : A --> w, wobei A ein Nichtterminal darstellt gesucht. Weiterhin sind keine Epsilon Regeln erlaubt.

Das Eingabe Alphabet ist {a,b,c}

Die Sprache ist L = {ucw | u, w ∈ {a,b,c} mit Anzahl von as in u = Anzahl von bs in u und  Anzahl von as in w = Anzahl von bs in w}

Meine Ideen bisher sind

S --> abSab

S --> baSba

S --> c

Aber das kommt ja nie zu einer endlichen Regelmenge

Answer 1

S -> c

S -> Wc

S -> cW

S -> WcW

W -> c

W -> ab

W -> Wab

W -> aWb

W -> abW

W -> ba

W -> Wba

W -> bWa

W -> baW

Das geht sicherlich auch mit weniger Regeln.

u, w ∈ {a,b,c}

Ich vermute du meinst u, w ∈ {a,b,c}^*. Sonst ist die Sprache endlich und es reicht eine reguläre Grammatik

Comments

Die Regeln

W -> aWb

W -> bWa

können die Sprache verlassen.

---

Nein, das können sie nicht.

---

(1) S -> Wc

(2) W -> aWb

(3) W -> c

ergibt:

S -> Wc -> aWbc -> acbc ∉ L

anderes Beispiel mit anderen Regeln:

(1) S -> Wc

(2) W -> ab

ergibt:

S -> Wc -> abc ∉ L

Habe ich etwas übersehen oder falsch verstanden?

---

acbc ∈ L  mit u = acb und w = ε.

---

Hm... ich habe mit u=a und w=bc acbc ∉ L geschlossen. Dabei bin ich davon ausgegangen, dass die Bedingung in der Angabe der Sprache L für alle Paare u, w gelten soll. Muss sie nur für ein Paar gelten, hast du recht und dieses Gegenbeispiel ist keines.

Das zweite Gegenbeispiel, dass ich angeführt habe, ist ohnehin keines.

---

{ f(a,b) | φ(a,b) } ist eine Abkürzung für { v | ∃a∃b (f(a,b) = v ∧ φ(a,b)) }.

Streng genommen muss noch angegeben werden, aus welcher Menge a, b und v stammen. Sonst dreht sich Bertrand Russell im Grab um.