Gegeben eine Grammatik mit den Regeln S -> a A, A -> S A und A -> b c d. Was ist zu tun?
- Gar nichts, alle Regeln sind bereits im GNF-Format.
- Die zweite Regel ist nicht korrekt: S muss durch a A (aus der ersten Regel) ersetzt werden: A -> a A A.
- Zweite und dritte Regel sind noch nicht korrekt. Für c und d muss es neue Nichtterminale und Regeln C -> c/ D->d geben.
In der zweiten Regel ersetzt man S durch a A (aus der ersten Regel): A -> a A A.
|
Antwort iii) ist richtig. Startet eine Regel mit einem Nichtterminal A so müssen für jede Regel in denen A die linke Regelseite ist
(sogenannte A-Regeln) neue Regeln eingeführt werden, in denen A durch die jeweils rechte Regelseite ersetzt wird.
Dieser Vorgang ist rekursiv, d.h. die jetzigen Regeln müssen noch nicht der GNF entsprechen.
Es gibt ein effizientes Verfahren, um alle Regeln effektiv umzuwandeln und keine Regel auszulassen.
|
