Ableiten von Wörtern bei Grammatiken in Chomsky-Normalform

Question

Mir ist aufgefallen, dass in Altklausuren  mit Aufgaben zur Chomsky-Normalform häufig in Auggabenteil a) das Umwandeln einer Garmmatik in CNF gefordert ist. Im Aufgabenteil b) soll dann ein Testwort abgeleitet werden, wobei dafür entweder die ursprüngliche Grammatik oder die Grammatik in CNF verwendet werden kann. Da es offensichtlich wenig Sinn macht ein potentiell falsches Zwischenergebnis zu verwenden hätte ich folgende Fragen:

1. Ist es im Allgemeinen einfacher ein Wort mit einer Grammatik in CNF abzuleiten?

2. Gibt es ein strukturiertes Vorgehen zum Ableiten von Wörtern?

Answer 1

Hallo,

Zur ersten Frage:

Eine CNF besitzt eine sehr eingeschränkte Regelmenge, d.h. Ableitungsmöglichkeiten, da lediglich erlaubt ist:  N -> NN | T. Damit erhält man ein etwas sequentielleres und strukturierteres Vorgehen beim Ableiten eines Testworts.

Im Gegensatz dazu sind bei beispielsweise Kontextfreien Grammatiken (aus denen oft  eine CNF abgeleitet wird) die Ableitungen von einem N beliebig. Daher können diese sehr unschön aussehen, müssen allerdings nicht.

Im Allgemeinen ist es daher sinnvoll von einer CNF auszugehen. Ist die ursprüngliche Grammatik aber direkt einleuchtend, kann auch diese verwendet werden.

Zur zweiten Frage:

Nein gibt es leider nicht. Es ist aber immer sinnvoll, sich vorab eine grobe Struktur zu überlegen, über welche Schritte das Testwort erreicht werden kann. 

Viele Grüße,

Timon (Tutor)