100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 6: Kontextfreie Grammatiken

Der vorliegende Vorlesungszuschnitt beschäftigt sich mit kontextfreien Grammatiken (Typ-2-Grammatiken). Dabei heißt eine Grammatik kontextfrei, wenn nur Produktionen erlaubt sind, die genau ein Nonterminalsymbol auf eine beliebige Kombination aus Nonterminal- und Terminalsymbolen abbilden. Bei diesen Grammatiken kann jede Produktion unabhängig von dem ?Kontext? des zu ersetzenden Zeichens in einem Wort angewendet werden ? es ist also für das Anwenden einer Produktion unerheblich, welche Zeichen um das zu ersetzende Zeichen herum stehen. Zudem wird auf die Chomsky-Normalform (CNF) eingegangen, deren Produktionen ein Nonterminalsymbol entweder auf zwei Nonterminalsymbole oder genau ein Terminalsymbol abbilden. Der Cocke-Younger-Kasami-(CYK)-Algorithmus wird beschrieben, mit dessen Hilfe entschieden werden kann, ob ein Wort von einer kontextfreien Grammatik erzeugt werden kann oder nicht. Die Voraussetzung hierfür ist, dass die entsprechende Grammatik in CNF vorliegt.