Kontextfreie Sprache

Als Kontextfreie Sprache (engl. context-free languages, CFL) werden formale Sprachen bezeichnet, die über eine kontextfreie Grammatik verfügen, die diese Sprache erzeugt. Eine kontextfreie Grammatik erlaubt einen definierten Leseprozess (Interpretation) einer Sprache. Insbesondere bei Programmiersprachen kann dazu ein Parser verwendet werden. Kontextfreie Sprachen werden auch als Typ-2-Sprachen der Chomsky-Hierarchie bezeichnet.

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 (vgl. LR(k)-Grammatik).

Beispiele

Einfache Beispiele für kontextfreie Sprachen sind die Sprachen $L_{1}=\{a^{n}b^{n}|n\in \mathbb {N} \}$ und $L_{2}=\{vv^{R}\mathbb {} \}$ (Palindrome).

Beispielsweise enthält die Sprache $L_{1}$ die Wörter: ab, aabb, aaabbb usw. Die Sprache $L_{2}$ enthält die Wörter aa, abba, abaaba, abbbba, anna, otto usw.

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 Grammatiken darstellen lassen.

Eigenschaften

Die Klasse der kontextfreien Sprachen ist abgeschlossen unter der

• Vereinigung
  • Konstruktion: Seien $G_{1}=(N_{1},T_{1},\Pi _{1},\{S_{1}\})$ und $G_{2}=(N_{2},T_{2},\Pi _{2},\{S_{2}\})$ kontextfrei. Neues Startsymbol S und neue Produktion $S::=S_{1}|S_{2}$. $\Rightarrow L(G_{1})\cup L(G_{2})=L(G)$ mit $G=(N_{1}\cup N_{2}\cup \{S\},T_{1}\cup T_{2},\{S::=S_{1}|S_{2}\}\cup \Pi _{1}\cup \Pi _{2},\{S\})$
• Spiegelung
• Konkatenation (Verkettung)
  • Konstruktion: Seien $G_{1}=(N_{1},T_{1},\Pi _{1},\{S_{1}\})$ und $G_{2}=(N_{2},T_{2},\Pi _{2},\{S_{2}\})$ kontextfrei. Neues Startsymbol S und neue Produktion $S::=S_{1}S_{2}$. $\Rightarrow L(G_{1})L(G_{2})=L(G)$ mit $G=(N_{1}\cup N_{2}\cup \{S\},T_{1}\cup T_{2},\{S::=S_{1}S_{2}\}\cup \Pi _{1}\cup \Pi _{2},\{S\})$
• Kleene-Stern
  • Konstruktion: Sei $G=(N,T,\Pi ,\{S\})$ kontextfrei. Neues Startsymbol $S_{neu}$ und neue Produktion $S_{neu}::=S_{neu}S$. $\Rightarrow L(G)^{*}=L(G_{1})$ mit $G_{1}=(N\cup \{S_{neu}\},T,\{S_{neu}::=S_{neu}S|\epsilon \}\cup \Pi ,\{S_{neu}\})$
• Anwendung von Homomorphismen
• Inverser Anwendung von inversen Homomorphismen
• Durchschnittbildung mit regulären Sprachen

Sie ist nicht abgeschlossen unter

• Durchschnitt
  • Seien $L=\{a^{n}b^{n}c^{m}|n\geq 0\wedge m\geq 0\}$ und $L'=\{a^{m}b^{n}c^{n}|n\geq 0\wedge m\geq 0\}$ kontextfrei. Dann ist $L\cap L'=\{a^{n}b^{n}c^{n}|n\geq 0\}$, jedoch nicht kontextfrei.
• Komplement
  • Seien $L_{1},L_{2}$ kontextfrei und kontextfreie Sprachen unter Komplementbildung abgeschlossen. Dann sind auch ${\overline {L_{1}}},{\overline {L_{2}}}$ kontextfrei. Wegen der Abgeschlossenheit unter Vereinigung und De Morgan folgt, dass ${\overline {L_{1}}}\cup {\overline {L_{2}}}$ und damit ${\overline {{\overline {L_{1}}}\cup {\overline {L_{2}}}}}=L_{1}\cap L_{2}$ kontextfrei ist.
• Anwendung von logarithmisch platzbeschränkter Reduktion
• Symmetrischer Differenz

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.

Typische Entscheidungsprobleme

Seien $L$, $L_{1}$ und $L_{2}$ gegebene kontextfreie Sprachen über dem Alphabet $\Sigma$. Dann ergeben sich folgende typische Problemstellungen:

• Wortproblem: Gehört ein Wort $w\in \Sigma ^{*}$ zu $L$?
• Leerheitsproblem: Ist $L$ die leere Menge?
• Endlichkeitsproblem: Besteht $L$ aus einer endlichen Menge von Wörtern ($\left|L\right|<\infty$)?

Die oben aufgezählten Probleme sind bei kontextfreien Sprachen entscheidbar. Das Äquivalenzproblem ($L_{1}=L_{2}$) ist ab einschließlich dieser Stufe der Chomsky-Hierarchie nicht mehr entscheidbar.

Weitergehende Eigenschaften

• DLIN $\subsetneq$ DCFL $\subsetneq$ CFL $\subsetneq$ GCSL $\subsetneq$ CSL
• REG $\subsetneq$ DLIN $\subsetneq$ LIN $\subsetneq$ CFL
• Für jedes $n\in \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 nachgewiesen, dass die Sprache sich nicht vollständig mit einer solchen Grammatik beschreiben lässt.

Literatur

• Uwe Schöning: Theoretische Informatik - kurzgefasst. 4. Auflage. Berlin 2003, Spektrum, ISBN 3-8274-1099-1.
• Stuart M. Shieber: Evidence against the context-freeness of natural language. In: Linguistics and Philosophy 8, 1985, 3, ISSN 0924-4662, S. 333–343.
• John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. überarbeitete Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5.
• Leonard Y. Liu, Peter Weiner: An Infinite Hierarchy of Intersections of Context-Free Languages. In: Mathematical Systems Theory 7, 1973, ISSN 0025-5661, S. 185–192.

Siehe auch

• Backus-Naur-Form, eine kompakte formale Metasprache zur Darstellung kontextfreier Grammatiken.

Weblinks

• CFL. In: Complexity Zoo. (englisch)