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.