Kontextfreie Sprache

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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.

Inhaltsverzeichnis

1 Definition
2 Charakterisierung
3 Beispiele
4 Eigenschaften
5 Weitergehende Eigenschaften
6 Natürliche Sprache
7 Literatur
8 Siehe auch

[Bearbeiten] Definition

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

[Bearbeiten] 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.

[Bearbeiten] Beispiele

Einfache Beispiele für kontextfreie Sprachen sind die Sprachen $L_1=\{a^nb^n|n\in\mathbb{N}\}$ und $L_2=\{v|v=v^{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.

[Bearbeiten] 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

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 (= Pumplemma) kann für eine Sprache gezeigt werden, dass sie nicht regulär bzw. kontextfrei ist.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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: 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.

[Bearbeiten] Siehe auch

Backus-Naur-Form

Automatentheorie: Formale Sprachen und Formale Grammatiken
Chomsky- Hierarchie	Grammatiken	Sprachen	Minimaler Automat
Typ-0	uneingeschränkt	rekursiv aufzählbar	Turingmaschine
	uneingeschränkt	rekursiv	Turingmaschine
Typ-1	kontextsensitiv	kontextsensitiv	linear beschränkt
Typ-2	kontextfrei	kontextfrei	Kellerautomat
Typ-3	Regulär	Regulär	Endlich
Jede Klasse einer Sprache oder Grammatik ist eine echte Teilmenge der Klasse darüber.