0 Daumen
262 Aufrufe

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

L = {w ∈ ∑* | #a(w) + (#b(w) = #c(w)}

#a(w) bedeutet die Anzahl an a's im Wort w.

Zeigen Sie, dass L kontextfrei ist, indem Sie eine kontextfreie Grammatik G angeben, mit L(G) = L. Geben Sie eine kurze Begründung Ihrer Wahl an.


Frage: Ich habe eine Verständnisfrage zu dieser Aufgabenstellung.

Ist es für mich erlaubt, eine Grammatik anzugeben, die nur folgende Wörter zulässt (a^+b^+c^+)* ?

Also, dass man immer nur solche Wörter produzieren kann: abcc oder abccabcc usw. ?

Oder muss ich wirklich alle Fälle abdecken, um die Aufgabe korrekt zu lösen? Also auch sowas wie: ccba, cabc etc.?


Weil wenn nicht, dann wäre das meine kontextfreie Grammatik:

R = {

S-> aX | ε,

X -> bY,

Y -> ccZ | ccS,

Z -> ε }

von

1 Antwort

0 Daumen
Oder muss ich wirklich alle Fälle abdecken, um die Aufgabe korrekt zu lösen? Also auch sowas wie: ccba, cabc etc.?

Ja

von 5,5 k

Für die Sprache

L = {wvc | w,v ∈ {a,b}* ∧ |w| > |v|}

habe ich jetzt folgende Grammatik erstellt:

G = ({S,K}, {a,b,c}, R, S) mit

R = {S -> aaSb | bbSa | baSa | abSa | baSb | abSb | aaKb | abKa | bbKa | baKa | baKb | abKb,

K -> c }


Das ist so möglich, oder?

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community