Theoretische Informatik

Chomsky-Normalform

einer kontextfreien Grammatik

 aufwärts

In manchen Fällen ist es erforderlich, dass die kontextfreie Grammatik in einer speziellen Form, der Chomsky-Normalform, vorliegt, so etwa für das CYK-Parsing-Verfahren oder für den Beweis des Pumping-Lemmas für kontextfreie Sprachen. Die Chomsky-Normalform ist benannt nach N. Chomskyzur Person.

Es gibt noch eine andere Normalform für kontextfreie Grammatiken, die Greibach-Normalform.

Chomsky-Normalform einer kontextfreien Grammatik

Definition:  Sei G = (V, T, P, S) eine kontextfreie Grammatik. G ist in Chomsky-Normalform, wenn jede ihrer Produktionen die Form

Xgeht über nachYZ    oder
Xgeht über nacha

mit X, Y, Z Element V und a Element T hat.

Als Ausnahme ist die Produktion S Pfeil nach rechts ε erlaubt, wobei dann das Startsymbol S nicht rekursiv sein darf.

Auf der rechten Seite jeder Produktion stehen also stets entweder genau zwei Variablen oder genau ein Terminal­zeichen. Obwohl die Form der Produktionen derart stark einge­schränkt ist, lassen sich mit Grammatiken in Chomsky-Normalform dennoch genau die kontext­freien Sprachen erzeugen.

Satz:  Zu jeder kontext­freien Grammatik gibt es eine äquivalente kontextfreie Grammatik in Chomsky-Normalform.

Zum Beweis dieses Satzes wird ein Verfahren benutzt, das eine beliebige kontextfreie Grammatik in die Chomsky-Normalform umformt, ohne dass sich die erzeugte Sprache ändert. Das Verfahren soll am Beispiel folgender kontext­freier Grammatik dargestellt werden:

Sgeht über nachC
Cgeht über nachaSb  |  ε

Diese Grammatik erzeugt die Sprache { anbn  |  n Element natürliche Zahlen0 }.

 

Umformung einer kontext­freien Grammatik in die Chomsky-Normalform
  1. Basis-Normalisierung

     

    Die Basis-Normalisierung umfasst die Schritte

    • Nutzlose Variablen entfernen
    • Rekursives Startsymbol entfernen
    • Epsilon-Produktionen entfernen
    • Ketten­produktionen entfernen

       

    Das Ergebnis der Basis-Normalisierung für die oben angegebene Grammatik ist die Grammatik

    S'geht über nachaSb  |  ab  |  ε
    Sgeht über nachaSb  |  ab

    mit S' als neuem Startsymbol.

     

  2. Terminal­zeichen überbrücken

    Als nächstes wird für jedes Terminal­zeichen eine neue Variable, quasi als "große Schwester"1), eingeführt. Alle Vorkommen von Terminal­zeichen in den Produktionen werden durch die entsprechenden großen Schwestern ersetzt, und schließlich werden neue Produktionen, in denen die großen Schwestern wieder in Terminal­zeichen überführt werden, hinzugefügt.

    Im Beispiel führen wir neue Variablen A und B als große Schwestern ein und lassen diese an die Stelle der Terminal­zeichen a und b treten. Ferner fügen wir entsprechende neue Produktionen hinzu, um wieder die Terminal­zeichen a und b zu erzeugen:

    S'geht über nachASB  |  AB  |  ε
    Sgeht über nachASB  |  AB
    Ageht über nacha
    Bgeht über nachb

     

  3. Produktionen aufspalten

    Schließlich werden die Produktionen S'geht über nachASB und Sgeht über nachASB, die auf der rechten Seite mehr als zwei Variablen enthalten, wie folgt aufgespalten, indem neue Variablen, hier D und E eingeführt werden:

    S'geht über nachAD
    Dgeht über nachSB

    sowie

    Sgeht über nachAE
    Egeht über nachSB

 

Die vollständige Grammatik in Chomsky-Normalform lautet somit:

S'geht über nachAD  |  AB  |  ε
Dgeht über nachSB
Sgeht über nachAE  |  AB
Egeht über nachSB
Ageht über nacha
Bgeht über nachb

 


1)  Eine schöne Metapher, gefunden in Lehr­materialien von H.U. Simon, Ruhr-Uni Bochum

 

Weiter:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 04.01.2010   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik