0 Daumen
279 Aufrufe

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

von

1 Antwort

+1 Daumen

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

von 2,0 k

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.

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
0 Antworten
0 Daumen
1 Antwort
Gefragt 16 Jan 2017 von Gast
0 Daumen
0 Antworten

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community