Gegeben sei die Grammatik

G = ({S, A, B},{a, b},S, {S → ASB | ε , A → aAS | a, B → SBS | A | bb}) .

Machen Sie sukzessiv folgende Schritte.

• Eliminieren Sie nicht nützliche Nicht-Terminalzeichen.
• Machen Sie Grammatik ε -frei.
• Eliminieren Sie Einheitsproduktionen.
• Bringen Sie die Grammatik in Chomsky-Normalform.