Kontextfreie Sprache
Eine formale Sprache ist genau dann kontextfrei, wenn eine kontextfreie Grammatik existiert, die diese Sprache erzeugt. 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.
| Inhaltsverzeichnis |
|
2 Eigenschaften 3 Natürliche Sprache 4 Literatur 5 Siehe auch |
Beispiele
Einfache Beispiele für kontextfreie Sprachen sind die Sprachen
und 
(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.
Eigenschaften
Die Klasse der kontextfreien Sprachen ist unter der Vereinigung, der Wortumkehrung und der Verkettung abgeschlossen. Sie ist nicht abgeschlossen unter Komplement und Schnitt.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.
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
- 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.
- J.E. Hopcroft: ''Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie" ISBN 3827370205
Siehe auch
