Kontextfreie Sprache

In d​er Theoretischen Informatik i​st eine kontextfreie Sprache (englisch context-free language, CFL) e​ine formale Sprache, d​ie durch e​ine kontextfreie Grammatik beschrieben werden kann. Eine kontextfreie Grammatik erlaubt e​inen definierten Leseprozess (Interpretation) v​on Ausdrücken e​iner formalen Sprache. Dabei k​ann zum e​inen entschieden werden, o​b ein Ausdruck d​en Regeln d​er Grammatik entspricht, u​nd zum anderen i​m Verlauf d​er Analyse e​in Syntaxbaum erstellt werden. Ein Programm, d​as dies leistet, heißt Parser. Parser werden insbesondere z​ur Verarbeitung v​on Programmiersprachen verwendet. Auch i​n der Computerlinguistik versucht man, natürliche Sprachen d​urch Regeln kontextfreier Grammatiken z​u beschreiben.

Kontextfreie Sprachen werden a​uch als Typ-2-Sprachen d​er Chomsky-Hierarchie bezeichnet. Die Klasse a​ller kontextfreien Sprachen beinhaltet d​ie regulären Sprachen (Typ-3-Sprachen) u​nd wird v​on der Klasse d​er kontextsensitiven Sprachen (Typ-1-Sprachen) umfasst.

Charakterisierung

Die Klasse d​er kontextfreien Sprachen i​st gleich d​er Klasse d​er von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Die v​on deterministischen Kellerautomaten akzeptierten Sprachen werden a​ls deterministisch kontextfreie Sprachen bezeichnet u​nd sind identisch m​it der Klasse d​er LR(k)-Sprachen (vgl. LR(k)-Grammatik).

Man spricht deshalb v​on kontextfreien Sprachen, w​eil die Regeln d​er kontextfreien Grammatiken i​mmer vom Kontext unabhängig angewendet werden, d​a jeweils a​uf den linken Seiten d​er Produktionsregeln n​ur ein Nichtterminal stehen darf. Das unterscheidet s​ie von kontextsensitiven Grammatiken, d​eren Regeln a​uch vom syntaktischen Kontext abhängen, a​lso auf d​en linken Seiten d​er Produktionsregeln a​uch Kombinationen v​on Nichtterminalen u​nd Terminalen stehen dürfen.

Beispiele

Besteht ein Alphabet aus den Symbolen ${\displaystyle a}$ und ${\displaystyle b}$, sind folgende Sprachen Beispiele für kontextfreie Sprachen:

• ${\displaystyle L_{1}=\{a^{n}b^{n}\mid n\in \mathbb {N} \}}$
• ${\displaystyle L_{2}=\{vv^{\text{R}}\mid v{\text{ besteht aus beliebig vielen }}a{\text{s und }}b{\text{s}}\}}$

Die Sprache ${\displaystyle L_{1}}$ enthält die Wörter: ${\displaystyle ab}$, ${\displaystyle aabb}$, ${\displaystyle aaabbb}$ usw., also immer so viele ${\displaystyle a}$s wie ${\displaystyle b}$s. Wählt man statt ${\displaystyle a}$ und ${\displaystyle b}$ die Symbole ${\displaystyle (}$ und ${\displaystyle )}$, entspricht das der korrekt verschachtelten Klammerung: etwa ${\displaystyle (())}$ oder ${\displaystyle ((()))}$.

Die Sprache ${\displaystyle L_{2}}$ enthält die Wörter ${\displaystyle aa}$, ${\displaystyle abba}$, ${\displaystyle abaaba}$, ${\displaystyle abbbba}$ usw., also alle symmetrischen Wörter. Da sie von vorne und hinten gelesen das gleiche Wort ergeben, sind es Palindrome.

Die Sprache ${\displaystyle L_{3}=\{a^{n}b^{n}c^{n}\mid n\in \mathbb {N} \}}$ ist kontextsensitiv, aber nicht kontextfrei.

Kontextfreie Sprachen finden i​n der Definition d​er Syntax v​on Programmiersprachen Anwendung, e​s lassen s​ich zum Beispiel arithmetische Ausdrücke u​nd allgemein korrekte Klammerstrukturen festlegen. Grenzen d​er kontextfreien Sprachen liegen b​ei kontextrelevanten Eigenschaften, w​ie z. B. d​er Typüberprüfung i​n Programmiersprachen, d​ie sich n​ur durch kontextsensitive Grammatiken darstellen lassen. In d​er Praxis verwendet m​an aber kontextfreie Parser m​it zusätzlichen Funktionen u​nd Datenstrukturen.

In der Computerlinguistik werden mit kontextfreien Grammatiken natürliche Sprachen nachgebildet. Besteht ein Alphabet aus Wörtern einer Sprache, zum Beispiel ${\displaystyle der,Baum,Satz}$, kann man mit wenigen Regeln einfache Nominalphrasen konstruieren: Durch die Regeln ${\displaystyle NP\rightarrow der\,N}$ und ${\displaystyle N\rightarrow Baum\mid Satz}$ sind ${\displaystyle der\,Baum}$ und ${\displaystyle der\,Satz}$ korrekte Ausdrücke in der Grammatik.

Eigenschaften

Die Klasse d​er kontextfreien Sprachen i​st abgeschlossen u​nter der

• Vereinigung
• Spiegelung
• Konkatenation (Verkettung)
• kleeneschen Hüllenbildung
• Anwendung von Homomorphismen
• Inverser Anwendung von Homomorphismen
• Durchschnittbildung mit regulären Sprachen

Sie i​st nicht abgeschlossen unter

• Durchschnitt
  • Gegenbeispiel: Die Sprachen ${\displaystyle L=\{a^{n}b^{n}c^{m}\mid n,m\in \mathbb {N} _{0}\}}$ und ${\displaystyle L'=\{a^{m}b^{n}c^{n}\mid n,m\in \mathbb {N} _{0}\}}$ sind kontextfrei. Aber ${\displaystyle L\cap L'=\{a^{n}b^{n}c^{n}\mid n\in \mathbb {N} _{0}\}}$ ist nicht kontextfrei.
• Komplement
  • Widerspruchsbeweis: Es wurde bereits gezeigt, dass es kontextfreie Sprachen ${\displaystyle L_{1},L_{2}}$ gibt, deren Schnitt ${\displaystyle L_{1}\cap L_{2}}$ nicht kontextfrei ist. Seien kontextfreie Sprachen unter Komplementbildung abgeschlossen. Dann sind auch ${\displaystyle {\overline {L_{1}}},{\overline {L_{2}}}}$ kontextfrei. Wegen der Abgeschlossenheit unter Vereinigung und De Morgan folgt, dass ${\displaystyle {\overline {L_{1}}}\cup {\overline {L_{2}}}}$ und damit ${\displaystyle {\overline {{\overline {L_{1}}}\cup {\overline {L_{2}}}}}=L_{1}\cap L_{2}}$ kontextfrei ist. Widerspruch: der Durchschnitt ${\displaystyle L_{1}\cap L_{2}}$ wurde als nicht kontextfrei vorausgesetzt.
• Anwendung von logarithmisch platzbeschränkter Reduktion
• Symmetrischer Differenz

Der Abschluss unter Vereinigung lässt sich durch Konstruktion einer neuen, wiederum kontextfreien Grammatik nachweisen: Seien ${\displaystyle G_{1}=(N_{1},T_{1},\Pi _{1},\{S_{1}\})}$ und ${\displaystyle G_{2}=(N_{2},T_{2},\Pi _{2},\{S_{2}\})}$ kontextfrei. Neues Startsymbol ${\displaystyle S}$ und neue Produktion ${\displaystyle S::=S_{1}|S_{2}}$. ${\displaystyle \Rightarrow L(G_{1})\cup L(G_{2})=L(G)}$ mit ${\displaystyle 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\})}$

Genauso kann man für zwei kontextfreie Sprachen die Abgeschlossenheit unter Konkatenation zeigen: Seien ${\displaystyle G_{1}=(N_{1},T_{1},\Pi _{1},\{S_{1}\})}$ und ${\displaystyle G_{2}=(N_{2},T_{2},\Pi _{2},\{S_{2}\})}$ kontextfrei. Neues Startsymbol ${\displaystyle S}$ und neue Produktion ${\displaystyle S::=S_{1}S_{2}}$. ${\displaystyle \Rightarrow L(G_{1})L(G_{2})=L(G)}$ mit ${\displaystyle 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\})}$

Auch die Anwendung von Kleene-* entspricht einer neuen, kontextfreien Grammatik: Sei ${\displaystyle G=(N,T,\Pi ,\{S\})}$ kontextfrei. Neues Startsymbol ${\displaystyle S_{\text{neu}}}$ und neue Produktion ${\displaystyle S_{\text{neu}}::=S_{\text{neu}}S}$. ${\displaystyle \Rightarrow L(G)^{*}=L(G_{1})}$ mit ${\displaystyle G_{1}=(N\cup \{S_{\text{neu}}\},T,\{S_{\text{neu}}::=S_{\text{neu}}S|\epsilon \}\cup \Pi ,\{S_{\text{neu}}\})}$

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. Ein solches Beispiel ist ${\displaystyle \{a^{n}b^{n}c^{n}\mid n\in \mathbb {N} _{0}\}}$. Pumping-Lemmas existieren jeweils in verschiedenen Varianten für reguläre und kontextfreie Sprachen. Für kontextfreie Sprachen beschreiben sie notwendige, aber nicht hinreichende Eigenschaften. Der Nachweis, dass eine formale Sprachen nicht kontextfrei ist, wird in der Regel über die Verletzung dieser notwendigen Eigenschaften geführt. Oft wird die untersuchte Sprache zunächst durch den Schnitt mit einer regulären Sprache geeignet ausgedünnt. Dieses Vorgehen ist durch den oben genannten Abschluss unter Schnitt mit regulären Sprachen gerechtfertigt.

Ein offenes Problem ist die Frage, ob die Menge der primitiven Wörter kontextfrei ist.[1] Dabei ist ein Wort über einem beliebigen Alphabet primitiv, wenn es keine Wiederholung eines anderen Wortes ist, also nicht die Form ${\displaystyle w^{n}}$ für ein beliebiges anderes, nicht-leeres Wort ${\displaystyle w}$ desselben Alphabetes und ein ganzzahliges ${\displaystyle n\geq 2}$ hat.[2]

Typische Entscheidungsprobleme

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

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

Die oben aufgezählten Probleme sind bei kontextfreien Sprachen entscheidbar (das Wortproblem durch den Cocke-Younger-Kasami-Algorithmus). Das Äquivalenzproblem (${\displaystyle L_{1}=L_{2}}$) ist ab einschließlich dieser Stufe der Chomsky-Hierarchie nicht mehr entscheidbar.

Weitergehende Eigenschaften

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

Natürliche Sprache

In d​er Linguistik werden kontextfreie Grammatiken a​uch zur Beschreibung d​er Syntax natürlicher Sprachen eingesetzt. Es w​urde aber z​um Beispiel für d​as Schweizerdeutsch nachgewiesen, d​ass die Sprache s​ich nicht vollständig m​it einer solchen Grammatik beschreiben lässt.[3] Vielfach werden a​ber in d​er Computerlinguistik kontextfreie Grammatiken (oder äquivalente Formalismen) m​it zusätzlichen Datenstrukturen a​uch für Sprachen w​ie Schweizerdeutsch verwendet.

Siehe auch

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

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.

Weblinks

• CFL. In: Complexity Zoo. (englisch)

Einzelnachweise

1. Pál Dömösi, Masami Ito: Context-Free Languages and Primitive Words. World Scientific Publishing Co Pte Ltd, Singapur 2014, ISBN 978-981-4271-66-0, S. 447 (Vorschau auf Google Books [abgerufen am 30. November 2015]).
2. Context-Free Languages and Primitive Words (siehe oben), S. 11 (Vorschau auf Google Books, abgerufen am 30. November 2015)
3. Stuart M. Shieber; Evidence against the context-freeness of natural language; In Linguistics and Philosophy 8; 1985 (pdf; 6,3 MB)