0 Daumen
717 Aufrufe

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.

Avatar von

1 Antwort

0 Daumen

Impliziert X0 → aXY|bXb|a die Regeln:

X0 → aXY, X0 → bXb, X0 → a?

Dann wäre deine Menge P ={

X0 → aXY, X0 → bXb, X0 → a, X → aXa, X →bY, X →ε, Y → bX0a, Y → aX0}

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community