Konstruieren Sie eine zu G äquivalente Grammatik in Chomsky-Normalform G = ({a, b}, {X0, X , Y }, P, X0)

Question

Aufgabe:

Betrachten Sie die kontextfreie Grammatik G = ({a, b}, {X0, X , Y }, P, X0) mit
P:

X0 → aXY|bXb|a

X → aXa|bY|ε

Y → bX0a|aX0

Konstruieren Sie eine zu G äquivalente Grammatik in Chomsky-Normalform.

Problem/Ansatz:

Komme mit der Aufgabe nicht klar und brauch eine Lösung um sie zu verstehen.

Answer 1

Impliziert X₀ → aXY|bXb|a die Regeln:

X₀ → aXY, X₀ → bXb, X₀ → a?

Dann wäre deine Menge P ={

X₀ → aXY, X₀ → bXb, X₀ → a, X → aXa, X →bY, X →ε, Y → bX₀a, Y → aX₀}

Für die Chomsky-Normalform darf deine Grammatik nur Regeln der Form A→a und A→AB enthalten. Wobei A aus N der Menge der nicht-Terminalsysmbole und a aus Sigma der Menge der Terminalsymbole stammen muss. Du musst  zuerst eine äquivalente ε-freie Grammatik konstruieren. Dann muss du noch die Regeln umformen die rechts mehr als zwei nicht-Terminalsysmbole stehen haben.