Suche Home Einstellungen Anmelden Hilfe

2.3.3 Greibach-Normalform (GNF):

(benannt nach Sheila Greibach) Die Javascriptelemente dieser Seite funktionieren nicht mit allen Browsern. Eine alternative Darstellung steht zur Verfügung. Ziel: Jede Regel hat die Form A - > a W mit A aus N, a aus T und W aus N* (-Regeln ausgenommen) Voraussetzung: Für jede kontextfreie Grammatik gibt es eine äquivalente Grammatik in GNF. Zur intuitiven Annäherung versuchen Sie, die folgenden Fragen zu beantworten:
• Gegeben eine Regel S -> b. Was ist zu tun? Gar nichts, die Regel ist bereits im GNF-Format. a muss durch A ersetzt werden In allen Regeln, in denen A als linke Regelseite vorkommt, muss es durch a ersetzt werden <<Klick hier>> für Antwortmöglichkeiten	Antwort i) ist richtig. Die Regel entspricht bereits dem GNF-Format. W ist in diesem Fall leer. <<Klick hier>> für Antwort
• Gegeben eine Regel X-> x y. Was ist zu tun? Gar nichts, die Regel ist bereits im GNF-Format. y muss zu einem Nichtterminal z.B. Y verändert werden; die modifizierte Regel heißt dann X -> x Y x muss zu einem Nichtterminal z.B. X verändert werden; die modifizierte Regel heißt dann X -> X y <<Klick hier>> für Antwortmöglichkeiten	Antwort ii) ist richtig. Die rechte Regelseite muss mit einem Terminalsymbol anfangen, darauf dürfen dann nur noch beliebig viele Nichtterminale folgen. Für das entsprechende Terminal wird ein noch nicht vorhandenes Nichtterminal eingeführt. Zusätzlich muss es die Regel Nichtterminal -> Terminal geben. <<Klick hier>> für Antwort
• 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. <<Klick hier>> für Antwortmöglichkeiten	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. <<Klick hier>> für Antwort
• Gegeben die Regeln Liste -> * Eintrag Liste und Eintrag -> foo (mit Liste und Eintrag aus N, * und foo aus T). Was ist zu tun? Gar nichts, die Regeln sind bereits im GNF-Format. foo muss Eintrag in der ersten Regel ersetzen: Liste -> * foo Liste. Für 'Eintrag Liste' muss ich ein neues Nichtterminal z.B. EiLi einführen. Anstelle der alten Regel gibt es zwei neue Regeln: Liste -> * EiLi und EiLi -> Eintrag Liste. <<Klick hier>> für Antwortmöglichkeiten	Antwort i) ist richtig. Die Regeln entsprechen voll dem GNF-Format. <<Klick hier>> für Antwort

Chomsky Normalform 1   2   3   4   5   6 Vorgehen

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