Suche Home Einstellungen Anmelden Hilfe

2.3.3 Greibach-Normalform (GNF):

Ziel: Jede Regel hat die Form A a W mit A aus N, a aus T und W aus N* (-Regeln ausgenommen) Start: kontextfreie Grammatik in CNF
	Ausgangspunkt: Eine Grammatik in Chomsky-Normalform enthält ausschließlich Regeln der Form1 A a   und   A B C Der erste Regeltyp entspricht bereits der GNF. Nur Regeln des zweiten Typs sind noch nicht im richtigen Format. Terminalsymbole werden nun unweigerlich mit einer Regel des Typs 1 eingeführt. Man wird nun also die Regeln vom Typ 2 so modifizieren, dass das Einfügen des Terminals vorweggenommen wird.
Die ursprünglichen Regeln führen u.a. zu folgenden Teilbäumen: Der "A-Baum" verknüpft mit einem "B-Baum" ergibt folgendes Bild. Eine modifizierte Regel führt zu einem zusammengezogen Baum.	Beispiel: Sei in einer Grammatik G folgende Regel: A B C Seien weiterhin die folgenden Regeln alle Regeln, in denen B das Nichtterminal der linken Regelseite ist (= alle "B-Regeln"): B a B A B Anstelle der 1. Regel führt man nun modifizierte Regeln ein. Diese entstehen, indem das B der rechten Regelseite (Regel 1) jeweils durch eine rechte Regelseite einer B-Regel ersetzt wird (Regel 2 und Regel 3). So erhält man die unten stehenden Regeln. Die generierte Sprache wird dadurch jedoch nicht verändert. A a C   und A A B C Warum ist das möglich? Hier nun einige allgemeine Betrachtungen. Gegeben sei eine Grammatik G mit einer A-Regel A w1 B w2. B β1 | β2 | ... | βn ist die Menge aller B-Regeln (w1, w2, β1, ... ,βn aus (N T)*, A und B aus N). Für eine neue Grammatik G' entfernt man aus P die Regel A w1 B w2 und fügt statt dessen A w1 β1 w2 | w1 β2 w2 | ... | w1 βn w2 ein. Es gilt L(G) = L(G'), wie man bei der Betrachtung der Ableitungsbäume leicht erkennen kann.

_____
A, B und C seien beliebige Nichtterminalsymbole der Grammatik; a ein beliebiges Terminalsymbol.

Greibach-Normalform 1   2   3   4   5   6 Weiteres Vorgehen

Benutzer: Gast • Besitzer: senn • Zuletzt geändert am: