Grammatiktransformationen: Chomsky-Normalform & Bereinigung
Beseitigung unzugänglicher Symbole
Algorithmus zur Entfernung unzugänglicher Symbole
Um unzugängliche Symbole aus einer Grammatik G = (N, T, P, S) zu entfernen und eine neue Grammatik G' = (N', T', P', S) zu erstellen, gehen Sie wie folgt vor:
Initialisierung
Initialisieren Sie die Menge der erreichbaren Nichtterminale N' (z.B. mit dem Startsymbol S) und die Menge der erreichbaren Produktionen P' als leer.
Iteration zur Ermittlung erreichbarer Symbole
Wiederholen Sie die folgenden Schritte, bis sich N' nicht mehr ändert:
- Für jedes Nichtterminal A ∈ N', wenn A → w eine Produktion in P ist, dann:
- Fügen Sie A → w zu P' hinzu.
- Für jedes Nichtterminal B, das in w vorkommt, fügen Sie B zu N' hinzu.
- Für jedes Terminal a, das in w vorkommt, werden
- Für jedes Nichtterminal A ∈ N', wenn A → w eine Produktion in P ist, dann: