Kontextfreie Sprache - LinkFang.de





Kontextfreie Sprache


In der Theoretischen Informatik ist eine kontextfreie Sprache (englisch context-free language, CFL) eine formale Sprache, die durch eine kontextfreie Grammatik beschrieben werden kann. Eine kontextfreie Grammatik erlaubt einen definierten Leseprozess (Interpretation) von Ausdrücken einer formalen Sprache. Dabei kann zum einen entschieden werden, ob ein Ausdruck den Regeln der Grammatik entspricht, und zum anderen im Verlauf der Analyse ein Syntaxbaum erstellt werden. Ein Programm, das dies leistet, heißt Parser. Parser werden insbesondere zur Verarbeitung von Programmiersprachen verwendet. Auch in der Computerlinguistik versucht man, natürliche Sprachen durch Regeln kontextfreier Grammatiken zu beschreiben.

Kontextfreie Sprachen werden auch als Typ-2-Sprachen der Chomsky-Hierarchie bezeichnet. Die Klasse aller kontextfreien Sprachen beinhaltet die regulären Sprachen (Typ-3-Sprachen) und wird von der Klasse der kontextsensitiven Sprachen (Typ-1-Sprachen) umfasst.

Man spricht deshalb von kontextfreien Sprachen, weil die Regeln der kontextfreien Grammatiken immer vom Kontext unabhängig angewendet werden. Das unterscheidet sie von kontextsensitiven Grammatiken, deren Regeln auch vom syntaktischen Kontext abhängen.

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

Besteht ein Alphabet aus den Symbolen [math]a[/math] und [math]b[/math], sind folgende Sprachen Beispiele für kontextfreie Sprachen:

  • [math]L_1=\{a^nb^n|n\in\mathbb{N}\}[/math]
  • [math]L_2=\{vv^{R}\mathbb| v\text{ besteht aus beliebig vielen }a\text{s und }b\text{s}\}[/math]

Die Sprache [math]L_1[/math] enthält die Wörter: [math]ab[/math], [math]aabb[/math], [math]aaabbb[/math] usw., also immer so viele [math]a[/math]s wie [math]b[/math]s. Wählt man statt [math]a[/math] und [math]b[/math] die Symbole [math]([/math] und [math])[/math], entspricht das der korrekt verschachtelten Klammerung: etwa [math](())[/math] oder [math]((()))[/math].

Die Sprache [math]L_2[/math] enthält die Wörter [math]aa[/math], [math]abba[/math], [math]abaaba[/math], [math]abbbba[/math] usw., also alle Wörter, die in der Mitte spiegelsymmetrisch sind. Da sie von vorne und hinten gelesen das gleiche Wort ergeben, sind es Palindrome.

Die Sprache [math]L_3=\{a^n b^n c^n|n\in\mathbb{N}\}[/math] ist kontextsensitiv, aber nicht kontextfrei.

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. In der Praxis verwendet man aber kontextfreie Parser mit zusätzlichen Funktionen und Datenstrukturen.

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

Eigenschaften

Die Klasse der kontextfreien Sprachen ist abgeschlossen unter der

Sie ist nicht abgeschlossen unter

  • Durchschnitt
    • Gegenbeispiel: Die Sprachen [math]L = \{a^nb^nc^m | n, m \in \N_{0}\}[/math] und [math]L' = \{a^mb^nc^n | n, m \in \N_{0}\}[/math] sind kontextfrei. Aber [math]L \cap L' = \{a^nb^nc^n | n \in \N_{0}\}[/math] ist nicht kontextfrei.
  • Komplement
    • Widerspruchsbeweis: Es wurde bereits gezeigt, dass es kontextfreie Sprachen [math]L_1, L_2[/math] gibt, deren Schnitt [math]L_1 \cap L_2[/math] nicht kontextfrei ist. Seien kontextfreie Sprachen unter Komplementbildung abgeschlossen. Dann sind auch [math]\overline{L_1}, \overline{L_2}[/math] kontextfrei. Wegen der Abgeschlossenheit unter Vereinigung und De Morgan folgt, dass [math]\overline{L_1} \cup \overline{L_2}[/math] und damit [math]\overline{\overline{L_1} \cup \overline{L_2}} = L_1 \cap L_2[/math] kontextfrei ist. Widerspruch: der Durchschnitt [math]L_1 \cap L_2[/math] 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 [math]G_1 = (N_1, T_1, \Pi_1, \{S_1\})[/math] und [math]G_2 = (N_2, T_2, \Pi_2, \{S_2\})[/math] kontextfrei. Neues Startsymbol S und neue Produktion [math]S ::= S_1|S_2[/math]. [math]\Rightarrow L(G_1) \cup L(G_2) = L(G)[/math] mit [math]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\})[/math]

Genauso kann man für zwei kontextfreie Sprachen die Abgeschlossenheit unter Konkatenation zeigen: Seien [math]G_1 = (N_1, T_1, \Pi_1, \{S_1\})[/math] und [math]G_2 = (N_2, T_2, \Pi_2, \{S_2\})[/math] kontextfrei. Neues Startsymbol S und neue Produktion [math]S ::= S_1S_2[/math]. [math]\Rightarrow L(G_1)L(G_2) = L(G)[/math] mit [math]G = (N_1 \cup N_2 \cup \{S\}, T_1 \cup T_2, \{S ::= S_1S_2\} \cup \Pi_1 \cup \Pi_2, \{S\})[/math]

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

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 [math]\{a^nb^nc^n | n \geq 0\}[/math]. 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 [math]w^n[/math] für ein beliebiges anderes, nicht-leeres Wort [math]w[/math] desselben Alphabetes und ein ganzzahliges [math]n \ge 2[/math] hat.[2]

Typische Entscheidungsprobleme

Seien [math]L[/math], [math]L_1[/math] und [math]L_2[/math] gegebene kontextfreie Sprachen über dem Alphabet [math]\Sigma[/math]. Dann ergeben sich folgende typische Problemstellungen:

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

Die oben aufgezählten Probleme sind bei kontextfreien Sprachen entscheidbar (das Wortproblem durch den Cocke-Younger-Kasami-Algorithmus). Das Äquivalenzproblem ([math]L_1=L_2[/math]) ist ab einschließlich dieser Stufe der Chomsky-Hierarchie nicht mehr entscheidbar.

Weitergehende Eigenschaften

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

Natürliche Sprache

In der Linguistik werden kontextfreie Grammatiken auch zur Beschreibung der Syntax 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.[3] Vielfach werden aber in der Computerlinguistik kontextfreie Grammatiken (oder äquivalente Formalismen) mit zusätzlichen Datenstrukturen auch für Sprachen wie Schweizerdeutsch verwendet.

Siehe auch

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

Literatur

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)

Kategorien: Sprachtyp | Theorie formaler Sprachen

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Kontextfreie Sprache (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.