Die Kontextfreien Sprachen (engl. context-free languages, CFL) sind eine Klasse der formalen Sprachen, sie werden auch als Typ-2-Sprachen der Chomsky-Hierarchie bezeichnet.

Definition

---

Eine formale Sprache ist genau dann kontextfrei, wenn eine kontextfreie Grammatik existiert, die diese Sprache erzeugt.

Charakterisierung

---

Die Klasse der kontextfreien Sprachen entspricht der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Die von deterministischen Kellerautomaten akzeptierten Sprachen werden als deterministisch kontextfreie Sprachen bezeichnet und sind identisch mit der Klasse der LR(k)-Sprachen.

Beispiele

---

Einfache Beispiele für kontextfreie Sprachen sind die Sprachen $L\_1=\backslash \{a^nb^n|n\backslash in\backslash mathbb\{N\}\backslash \}$ und $L\_2=\backslash \{v|v=v^\{-1\}\backslash \}$ (Palindrome). Kontextfreie Sprachen finden in der Definition der Syntax von Programmiersprachen Anwendung, es lassen sich zum Beispiel arithmetische Ausdrücke und allgemein korrekte Klammerstrukturen festlegen. Grenzen der kontextfreien Sprachen liegen bei kontextrelevanten Eigenschaften, wie z.B. der Typüberprüfung in Programmiersprachen, die sich nur durch kontextsensitive Sprachen darstellen lassen.

Eigenschaften

---

Die Klasse der kontextfreien Sprachen ist abgeschlossen unter der

• Vereinigung
• Spiegelung
• Konkatenation (verkettung)
• Anwendung von Homomorphismen
• Inverser Anwendung von inversen Homomorphismen
• Durchschnittbildung mit regulären Sprachen

Sie ist nicht abgeschlossen unter

• Komplement
• Durchschnitt
• Anwendung von logarithmisch platzbeschränkter Reduktion

Jede reguläre Sprache ist auch kontextfrei, da jede reguläre Grammatik auch eine kontextfreie Grammatik ist. Es existieren kontextsensitive Sprachen, die nicht kontextfrei sind. Durch das sogenannte Pumping-Lemma kann für eine Sprache gezeigt werden, dass sie nicht regulär bzw. kontextfrei ist.

Weitergehende Eigenschaften

---

• DLIN $\backslash subsetneq$ DCFL $\backslash subsetneq$ CFL $\backslash subsetneq$ GCSL $\backslash subsetneq$ CSL
• REG $\backslash subsetneq$ DLIN $\backslash subsetneq$ LIN $\backslash subsetneq$ CFL
• Für jedes $n\backslash in\backslash mathbb\{N\}$ gibt es Sprachen, die sich als Schnitt von $n$ kontextfreien Sprachen darstellen lassen aber nicht als Schnitt von $n-1$ kontextfreien Sprachen.

Natürliche Sprache

---

In der Linguistik werden kontextfreie Grammatiken auch zur Beschreibung der Grammatik natürlicher Sprachen eingesetzt. Es wurde aber zum Beispiel für das Schweizerdeutsch bewiesen, dass die Sprache sich nicht vollständig mit einer solchen Grammatik beschreiben lässt.

Literatur

---

• Uwe Schöning: Theoretische Informatik kurzgefasst, 4. Auflage, Spektrum, ISBN 3827410991
• S.M. Shieber: Evidence against the context-freeness of natural language. Linguistics and Philosophy, 8, 333-343.
• John E. Hopcroft: ''Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie" ISBN 3827370205

Siehe auch

---

• Backus-Naur-Form

Linguistik | Formale Sprachen

Bezkontextový jazyk | Context-free language | Yhteydetön kieli | שפה חופשית הקשר | Linguaggio context-free | Język bezkontekstowy | Limbaje independente de context