Zeigen, dass L kontextfrei ist, indem man eine kontextfreie Grammatik G angibt, mit L(G) = L.

Question

Frage:

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

L = { wvu | w ∈ {a,b}* ∧ v ∈ {a,c}* ∧ |w| = |v| ∧ u ∈ {d}*}

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

Ich bin auf folgende Grammatik gekommen: G = ({S,P,K,D}, {a,b,c,d}, R, S)

mit R =

{

S -> ε | PSK | PK,

P ->  a | b,

K -> a | c | aD | cD,

D -> dD | d | ε}

Ist das korrekt?

Comments

Puuuush. @Oswald, bitte, wenn du Zeit hast, über eine Antwort wäre ich dir sehr dankbar.

Answer 1

\(\begin{aligned} & S\\ \to & PSK\\ \to & PPKK\\ \to & PPcDK\\ \to & bbcdc \end{aligned}\)