Kontextfrei

In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: OMA-Verständlichkeit bei den Beispielen ausbauen Du kannst Wikipedia helfen, indem du sie recherchierst und einfügst.

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^nb^n|n\in\mathbb{N}\}$ und $L_2=\{vv^{R}\mathbb{}\}$ (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 Grammatiken darstellen lassen.

Eigenschaften

Die Klasse der kontextfreien Sprachen ist abgeschlossen unter der

• Vereinigung
  • Konstruktion: Seien G₁ = (N₁,T₁,Π₁,{S₁}) und G₂ = (N₂,T₂,Π₂,{S₂}) kontextfrei. Neues Startsymbol S und neue Produktion S:: = S₁ | S₂. $\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₁ = (N₁,T₁,Π₁,{S₁}) und G₂ = (N₂,T₂,Π₂,{S₂}) kontextfrei. Neues Startsymbol S und neue Produktion S:: = S₁S₂. $\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_1S_2\} \cup \Pi_1 \cup \Pi_2, \{S\})$
• Kleene-Stern
  • Konstruktion: Sei G = (N,T,Π,{S}) kontextfrei. Neues Startsymbol S_neu und neue Produktion S_neu:: = S_neuS. $\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^nb^nc^m | n \geq 0 \wedge m \geq 0\}$ und $L' = \{a^mb^nc^n | n \geq 0 \wedge m \geq 0\}$ kontextfrei. Dann ist $L \cap L' = \{a^nb^nc^n | n \geq 0\}$, jedoch nicht kontextfrei.
• Komplement
  • Seien L₁,L₂ 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₁ und L₂ gegebene kontextfreie Sprachen über dem Alphabet Σ. 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₁ = L₂) 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, Spektrum, ISBN 3827410991
• S.M. Shieber: Evidence against the context-freeness of natural language. In Linguistics and Philosophy 8, 333-343.
• John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. ISBN 3827370205
• Leonard Y. Liu und Peter Weiner: An Infinite Hierarchy of Intersections of Context-Free Languages. In: Mathematical Systems Theory 7, 185-192, 1973.

Siehe auch

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