Theoretische Informatik

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. Chomsky.

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

X		YZ	oder
X		a

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

Als Ausnahme ist die Produktion S → ε 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 Terminalzeichen. Obwohl die Form der Produktionen derart stark eingeschränkt ist, lassen sich mit Grammatiken in Chomsky-Normalform dennoch genau die kontextfreien Sprachen erzeugen.

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 kontextfreier Grammatik dargestellt werden:

S		C
C		aSb  |  ε

Diese Grammatik erzeugt die Sprache { aⁿbⁿ  |  n ∈ ℕ₀ }.

Umformung einer kontextfreien Grammatik in die Chomsky-Normalform

1. Basis-Normalisierung

    

   Die Basis-Normalisierung umfasst die Schritte

   • Nutzlose Variablen entfernen
   • Rekursives Startsymbol entfernen
   • Epsilon-Produktionen entfernen
   • Kettenproduktionen entfernen

      

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

   S'		aSb  |  ab  |  ε
   S		aSb  |  ab

   mit S' als neuem Startsymbol.

    

2. Terminalzeichen überbrücken

   Als nächstes wird für jedes Terminalzeichen eine neue Variable, quasi als "große Schwester"¹), eingeführt. Alle Vorkommen von Terminalzeichen 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 Terminalzeichen ü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 Terminalzeichen a und b treten. Ferner fügen wir entsprechende neue Produktionen hinzu, um wieder die Terminalzeichen a und b zu erzeugen:

   S'		ASB  |  AB  |  ε
   S		ASB  |  AB
   A		a
   B		b

    

3. Produktionen aufspalten

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

   S'		AD
   D		SB

   sowie

   S		AE
   E		SB

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

S'		AD  |  AB  |  ε
D		SB
S		AE  |  AB
E		SB
A		a
B		b