kontextfreien

Kontextfreiheit bezeichnet eine Klasse formaler Grammatiken und der von ihnen erzeugten Sprachen. Eine kontextfreie Grammatik (CFG) besteht aus einer Menge von Variablen V, einem Alphabet der Terminale Σ, einer Menge von Produktionsregeln R und dem Startsymbol S ∈ V. Jede Regel hat die Form A → α, wobei A eine Variable ist und α eine Kette aus Variablen und Terminalsymbolen. Die von einer CFG erzeugte Sprache besteht aus allen Wörtern aus Σ, die aus dem Startsymbol durch Ableitungen gemäß R ableitbar sind.

Kontextfreie Sprachen (CFL) umfassen viele Programmier- und Auszeichnungssprachen. Sie lassen sich durch Parse-Bäume darstellen; die Ableitung entspricht dem Aufbau des Baums. Kontextfreie Grammatiken werden von Pushdown-Automaten erkannt, die einen endlichen Zustandsspeicher in Form eines Stacks verwenden. Dadurch eignen sie sich gut zur Modellierung verschachtelter Strukturen wie Klammerausdrücken oder verschachtelten Anweisungen.

Wichtige Eigenschaften umfassen die Tatsache, dass CFLs unter Vereinigung, Konkatenation und Kleene-Stern abgeschlossen sind, aber nicht unter Komplement. Sie sind unter dem Schnitt mit regulären Sprachen abgeschlossen. Das Memberschaftsproblem ist entscheidbar; gängige Verfahren sind der CYK-Algorithmus (für Grammatiken in Chomsky-Normalform) und der Earley-Parser. CFGs können mehrdeutig sein; die Bestimmung der Mehrdeutigkeit ist im Allgemeinen unentscheidbar. Die Äquivalenz zweier CFGs ist unentscheidbar, ebenso die Universialität (ob die Grammatik alle Wörter einer gegebenen Sprache erzeugt).

Historisch stammen die Konzepte aus der Chomsky-Sprachtheorie, die Noam Chomsky in den 1950er Jahren entwickelte. Anwendungen finden sich in Compilern, Parsern, Übersetzungswerkzeugen und der natürlichen Sprachverarbeitung, wo kontextfreie Strukturen zur Modellierung syntaktischer Ebenen dienen.