Suche Home Einstellungen Anmelden Hilfe  

2.3.3 Greibach-Normalform (GNF)

(benannt nach Sheila Greibach)

Ziel: Jede Regel hat die Form A - > a W mit A aus N, a aus T und W aus N* (epsilon-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?
  1. Gar nichts, die Regel ist bereits im GNF-Format.
  2. a muss durch A ersetzt werden
  3. In allen Regeln, in denen A als linke Regelseite vorkommt, muss es durch a ersetzt werden

 Antwort
Gegeben eine Regel X-> x y. Was ist zu tun?
  1. Gar nichts, die Regel ist bereits im GNF-Format.
  2. y muss zu einem Nichtterminal z.B. Y verändert werden; die modifizierte Regel heißt dann X -> x Y
  3. x muss zu einem Nichtterminal z.B. X verändert werden; die modifizierte Regel heißt dann X -> X y

 Antwort
Gegeben eine Grammatik mit den Regeln S -> a A, A -> S A und A -> b c d. Was ist zu tun?
  1. Gar nichts, alle Regeln sind bereits im GNF-Format.
  2. Die zweite Regel ist nicht korrekt: S muss durch a A (aus der ersten Regel) ersetzt werden: A -> a A A.
  3. 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
Gegeben die Regeln Liste -> * Eintrag Liste und Eintrag -> foo (mit Liste und Eintrag aus N, * und foo aus T). Was ist zu tun?
  1. Gar nichts, die Regeln sind bereits im GNF-Format.
  2. foo muss Eintrag in der ersten Regel ersetzen: Liste -> * foo Liste.
  3. 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.
 Antwort

Chomsky Normalform 1   2   3   4   5   6 Vorgehen

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