• Artikel
• Bearbeiten
• Historie
• Druckansicht

Ableitungsbaum aus Chomsky Normalform

Dies ist ein Kochrezept zum Zeichnen eines Ableitungsbaumes mit Hilfe der Chomsky-Normalform? und einer Beispieleingabe.

Die Normalform besitzt folgende Produktionen?:

S -> HB
S -> AB
S -> BA
S -> GA
H -> AS
G -> BS

Das Wort lautet: aaBAbb

Wir beginnen also mit dem a und suchen nach einer Produktion mit einem 'A' auf der linken Seite.

Zur Wahl stehen H->AS und S->AB - doch wie treffen wir die Entscheidung?
Versuchen wir es zuerst mit S->AB

Wie man sieht kann man den Baum nun nicht mehr erweitern, da es keine Produktionen aus B gibt - B führt nirgends hin.
Also wählen wie die Alternative und versuchen H->AS

Das nächste Zeichen im Wort ist wieder ein 'a'. Erweitern können wir im aktuellen Baum nur (S).

Von (S) haben wir generell wieder die folgenden Möglichkeiten: S->HB, S->AB, S->GA.
AB und GA haben alle keine Nachfolger. Also versuchen wir HB. Wir sehen schon, dass H weiter aus AS zeigt und wir somit unser gesuchtes 'a' allein durch Linksableitungen gefunden haben.

Als nächstes suchen wir das 'B'. Als Möglichkeit um fortzufahren bleibt uns nur das (S). Wenn wir im Hinterkopf behalten, dass wir im darauf folgenden Schritt wieder ein 'A' benötigen, schlagen wir zwei Fliegen mit einer Klappe. S->BA wird verwendet.

Da uns auch auffällt, dass das B schon expandiert ist, können wir dieses ebenfalls direkt abhaken.

Aktuell haben wir das Wort aaBAb abgebildet. Es fehlt nur noch ein weiteres B.
Wir stellen fest, dass wir keine Bäume mehr expandiere können und müssen nun die Wurzel verschieben. Wir nutzen S->HB - Über dem (H) fügen wir das (S) ein und neben dem (H) entsteht dadurch das B.

Wir sind fertig.
Der entstehende Ableitungsbaum sieht wie folgt aus: