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 -> ε }
