Kontextfreie Sprache

Grundidee und Einordnung

Eine kontextfreie Sprache, kurz CFL von englisch context-free language, ist in der Theoretischen Informatik eine formale Sprache, die durch eine kontextfreie Grammatik beschrieben werden kann. Eine formale Sprache besteht aus Wörtern über einem Alphabet; eine Grammatik legt Regeln fest, nach denen solche Wörter gebildet werden dürfen.

Kontextfreie Grammatiken sind wichtig, weil sie einen definierten Leseprozess für Ausdrücke ermöglichen. Dabei kann entschieden werden, ob ein Ausdruck den Regeln entspricht, und während der Analyse kann ein Syntaxbaum erstellt werden. Ein Programm, das das leistet, heißt Parser. Parser werden besonders zur Verarbeitung von Programmiersprachen verwendet. Auch in der Computerlinguistik versucht man, natürliche Sprachen mithilfe kontextfreier Grammatiken zu beschreiben.

In der Chomsky-Hierarchie heißen kontextfreie Sprachen auch Typ-2-Sprachen. Sie enthalten alle regulären Sprachen, also Typ-3-Sprachen, und liegen selbst innerhalb der kontextsensitiven Sprachen, also Typ-1-Sprachen.

Charakterisierung

Die Klasse der kontextfreien Sprachen ist genau die Klasse der Sprachen, die von nichtdeterministischen Kellerautomaten akzeptiert werden. Ein Kellerautomat ist ein Automat mit zusätzlichem Speicher in Form eines Kellers, also einer Stapelstruktur. Nichtdeterministisch bedeutet, dass der Automat in einer Situation mehrere mögliche nächste Schritte haben kann.

Die Sprachen, die von deterministischen Kellerautomaten akzeptiert werden, heißen deterministisch kontextfreie Sprachen. Sie sind identisch mit der Klasse der LR(k)-Sprachen.

Der Name „kontextfrei“ kommt daher, dass die Regeln einer kontextfreien Grammatik unabhängig vom Kontext angewendet werden. Auf der linken Seite einer Produktionsregel darf jeweils nur ein Nichtterminal stehen. Ein Nichtterminal ist ein Hilfssymbol der Grammatik, das weiter ersetzt werden kann. Das unterscheidet kontextfreie Grammatiken von kontextsensitiven Grammatiken: Dort dürfen auf der linken Seite auch Kombinationen von Nichtterminalen und Terminalen stehen, sodass Regeln vom syntaktischen Kontext abhängen können.

Beispiele und Anwendungen

Für ein Alphabet mit den Symbolen a und b sind typische Beispiele kontextfreier Sprachen:

• L_1 = {a^n b^n | n ∈ N}
• L_2 = {vv^R | v besteht aus beliebig vielen a und b}

Die Sprache L_1 enthält Wörter wie ab, aabb, aaabbb usw. In jedem Wort stehen zuerst genau so viele a wie danach b. Wenn man statt a und b die Symbole ( und ) wählt, entspricht dies korrekt verschachtelter Klammerung, zum Beispiel (()) oder ((())).

Die Sprache L_2 enthält Wörter wie aa, abba, abaaba, abbbba usw. Es handelt sich um symmetrische Wörter, die von vorne und hinten gelesen gleich sind; solche Wörter heißen Palindrome.

Die Sprache L_3 = {a^n b^n c^n | n ∈ N} ist dagegen kontextsensitiv, aber nicht kontextfrei. Sie zeigt eine Grenze kontextfreier Sprachen: Drei voneinander abhängige gleich große Blöcke können nicht mehr mit einer kontextfreien Sprache erfasst werden.

Kontextfreie Sprachen werden zur Definition der Syntax von Programmiersprachen eingesetzt. So lassen sich arithmetische Ausdrücke und allgemein korrekte Klammerstrukturen beschreiben. Grenzen treten bei kontextrelevanten Eigenschaften auf, etwa bei der Typüberprüfung in Programmiersprachen. Solche Eigenschaften lassen sich nur durch kontextsensitive Grammatiken darstellen. In der Praxis verwendet man jedoch oft kontextfreie Parser zusammen mit zusätzlichen Funktionen und Datenstrukturen.

In der Computerlinguistik können mit kontextfreien Grammatiken einfache Strukturen natürlicher Sprache modelliert werden. Wenn ein Alphabet aus Wörtern wie der, Baum und Satz besteht, können die Regeln NP → der N und N → Baum | Satz die Nominalphrasen der Baum und der Satz erzeugen.

Abschlusseigenschaften und Grenzen

Die Klasse der kontextfreien Sprachen ist unter mehreren Operationen abgeschlossen. Das bedeutet: Wendet man diese Operation auf kontextfreie Sprachen an, erhält man wieder eine kontextfreie Sprache. Abgeschlossen ist sie unter Vereinigung, Spiegelung, Konkatenation, kleenescher Hüllenbildung, Anwendung von Homomorphismen, inverser Anwendung von Homomorphismen und Durchschnittbildung mit regulären Sprachen.

Nicht abgeschlossen ist die Klasse unter Durchschnitt, Komplement, Anwendung von logarithmisch platzbeschränkter Reduktion und symmetrischer Differenz. Ein Gegenbeispiel für den Durchschnitt sind die kontextfreien Sprachen L = {a^n b^n c^m | n,m ∈ N_0} und L' = {a^m b^n c^n | n,m ∈ N_0}. Ihr Schnitt ist L ∩ L' = {a^n b^n c^n | n ∈ N_0}, und diese Sprache ist nicht kontextfrei.

Der fehlende Abschluss unter Komplement lässt sich über einen Widerspruch mit De Morgan begründen: Wären kontextfreie Sprachen unter Komplement abgeschlossen, dann wären bei kontextfreien L_1 und L_2 auch ihre Komplemente kontextfrei. Wegen des Abschlusses unter Vereinigung wäre dann auch die Vereinigung der Komplemente kontextfrei, und ihr Komplement wäre nach De Morgan L_1 ∩ L_2. Damit müsste jeder Durchschnitt kontextfreier Sprachen wieder kontextfrei sein, was falsch ist.

Der Abschluss unter Vereinigung, Konkatenation und Kleene-* kann jeweils durch Konstruktion einer neuen kontextfreien Grammatik gezeigt werden. Für die Vereinigung zweier Grammatiken G_1 und G_2 führt man ein neues Startsymbol S mit der Produktion S ::= S_1 | S_2 ein. Für die Konkatenation nutzt man S ::= S_1 S_2. Für L(G)^* führt man ein neues Startsymbol S_neu mit S_neu ::= S_neu S | ε ein.

Jede reguläre Sprache ist auch kontextfrei, weil jede reguläre Grammatik zugleich eine kontextfreie Grammatik ist. Es gibt aber kontextsensitive Sprachen, die nicht kontextfrei sind, zum Beispiel {a^n b^n c^n | n ∈ N_0}. Pumping-Lemmas für kontextfreie Sprachen beschreiben notwendige, aber nicht hinreichende Eigenschaften. Um zu zeigen, dass eine Sprache nicht kontextfrei ist, weist man meistens nach, dass sie diese notwendigen Eigenschaften verletzt. Oft wird die Sprache dafür zuerst durch Schnitt mit einer regulären Sprache passend eingeschränkt, was wegen des Abschlusses unter Schnitt mit regulären Sprachen erlaubt ist.

Ein offenes Problem ist, ob die Menge der primitiven Wörter kontextfrei ist. Ein Wort ist primitiv, wenn es keine Wiederholung eines anderen nicht-leeren Wortes ist, also nicht die Form w^n für ein anderes Wort w desselben Alphabetes und ein ganzzahliges n ≥ 2 hat.

Entscheidungsprobleme

Für gegebene kontextfreie Sprachen L, L_1 und L_2 über einem Alphabet Σ werden typische Entscheidungsprobleme untersucht. Beim Wortproblem fragt man, ob ein Wort w ∈ Σ* zu L gehört. Beim Leerheitsproblem fragt man, ob L die leere Menge ist. Beim Endlichkeitsproblem fragt man, ob L nur endlich viele Wörter enthält, also |L| < ∞.

Diese drei Probleme sind bei kontextfreien Sprachen entscheidbar. Das Wortproblem kann mit dem Cocke-Younger-Kasami-Algorithmus entschieden werden.

Nicht entscheidbar ist dagegen ab dieser Stufe der Chomsky-Hierarchie das Äquivalenzproblem. Dabei geht es um die Frage, ob zwei kontextfreie Sprachen gleich sind, also L_1 = L_2 gilt.

Weitere Beziehungen und natürliche Sprache

Für verschiedene Sprachklassen gelten echte Inklusionen. Im Artikel werden unter anderem genannt:

• DLIN ⊊ DCFL ⊊ CFL ⊊ GCSL ⊊ CSL
• REG ⊊ DLIN ⊊ LIN ⊊ CFL

Dabei steht REG für reguläre Sprachen, CFL für kontextfreie Sprachen, DCFL für deterministisch kontextfreie Sprachen und CSL für kontextsensitive Sprachen. Das Zeichen ⊊ bedeutet, dass die linke Klasse echt in der rechten enthalten ist, also nicht gleich groß ist.

Außerdem gilt: Für jedes n ∈ N gibt es Sprachen, die sich als Schnitt von n kontextfreien Sprachen darstellen lassen, aber nicht als Schnitt von n - 1 kontextfreien Sprachen.

In der Linguistik werden kontextfreie Grammatiken zur Beschreibung der Syntax natürlicher Sprachen verwendet. Für Schweizerdeutsch wurde jedoch nachgewiesen, dass sich die Sprache nicht vollständig mit einer solchen Grammatik beschreiben lässt. In der Computerlinguistik werden trotzdem häufig kontextfreie Grammatiken oder äquivalente Formalismen mit zusätzlichen Datenstrukturen auch für Sprachen wie Schweizerdeutsch eingesetzt.