www.wikidata.de-de.nina.az

Kontextfreie Sprache In der Theoretischen Informatik ist eine kontextfreie Sprache englisch context free language CFL ei

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.

Charakterisierung Bearbeiten

Die Klasse der kontextfreien Sprachen ist gleich 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).

Man spricht deshalb von kontextfreien Sprachen, weil die Regeln der kontextfreien Grammatiken immer vom Kontext unabhängig angewendet werden, da jeweils auf den linken Seiten der Produktionsregeln nur ein Nichtterminal stehen darf. Das unterscheidet sie von kontextsensitiven Grammatiken, deren Regeln auch vom syntaktischen Kontext abhängen, also auf den linken Seiten der Produktionsregeln auch Kombinationen von Nichtterminalen und Terminalen stehen dürfen.

Beispiele Bearbeiten

Besteht ein Alphabet aus den Symbolen und , sind folgende Sprachen Beispiele für kontextfreie Sprachen:

Die Sprache enthält die Wörter: , , usw., also immer so viele s wie s. Wählt man statt und die Symbole und , entspricht das der korrekt verschachtelten Klammerung: etwa oder .

Die Sprache enthält die Wörter , , , usw., also alle symmetrischen Wörter. Da sie von vorne und hinten gelesen das gleiche Wort ergeben, sind es Palindrome.

Die Sprache 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 , kann man mit wenigen Regeln einfache Nominalphrasen konstruieren: Durch die Regeln und sind und korrekte Ausdrücke in der Grammatik.

Eigenschaften Bearbeiten

Die Klasse der kontextfreien Sprachen ist abgeschlossen unter der

Sie ist nicht abgeschlossen unter

Der Abschluss unter Vereinigung lässt sich durch Konstruktion einer neuen, wiederum kontextfreien Grammatik nachweisen: Seien und kontextfrei. Neues Startsymbol und neue Produktion . mit

Genauso kann man für zwei kontextfreie Sprachen die Abgeschlossenheit unter Konkatenation zeigen: Seien und kontextfrei. Neues Startsymbol und neue Produktion . mit

Auch die Anwendung von Kleene-* entspricht einer neuen, kontextfreien Grammatik: Sei kontextfrei. Neues Startsymbol und neue Produktion . mit

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 . 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. Dabei ist ein Wort über einem beliebigen Alphabet primitiv, wenn es keine Wiederholung eines anderen Wortes ist, also nicht die Form für ein beliebiges anderes, nicht-leeres Wort desselben Alphabetes und ein ganzzahliges hat.

Typische Entscheidungsprobleme Bearbeiten

Seien , und gegebene kontextfreie Sprachen über dem Alphabet . Dann ergeben sich folgende typische Problemstellungen:

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

Weitergehende Eigenschaften Bearbeiten

  • DLIN DCFL CFL GCSL CSL
  • REG DLIN LIN CFL
  • Für jedes gibt es Sprachen, die sich als Schnitt von kontextfreien Sprachen darstellen lassen, aber nicht als Schnitt von kontextfreien Sprachen.

Natürliche Sprache Bearbeiten

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

Siehe auch Bearbeiten

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

Literatur Bearbeiten

  • 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 Bearbeiten

  • CFL. In: Complexity Zoo. (englisch)

Einzelnachweise Bearbeiten

  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)
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 Ausdrucken 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 heisst Parser Parser werden insbesondere zur Verarbeitung von Programmiersprachen verwendet Auch in der Computerlinguistik versucht man naturliche 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 regularen Sprachen Typ 3 Sprachen und wird von der Klasse der kontextsensitiven Sprachen Typ 1 Sprachen umfasst Inhaltsverzeichnis 1 Charakterisierung 2 Beispiele 3 Eigenschaften 4 Typische Entscheidungsprobleme 5 Weitergehende Eigenschaften 6 Naturliche Sprache 7 Siehe auch 8 Literatur 9 Weblinks 10 EinzelnachweiseCharakterisierung BearbeitenDie Klasse der kontextfreien Sprachen ist gleich 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 Man spricht deshalb von kontextfreien Sprachen weil die Regeln der kontextfreien Grammatiken immer vom Kontext unabhangig angewendet werden da jeweils auf den linken Seiten der Produktionsregeln nur ein Nichtterminal stehen darf Das unterscheidet sie von kontextsensitiven Grammatiken deren Regeln auch vom syntaktischen Kontext abhangen also auf den linken Seiten der Produktionsregeln auch Kombinationen von Nichtterminalen und Terminalen stehen durfen Beispiele BearbeitenBesteht ein Alphabet aus den Symbolen a displaystyle a nbsp und b displaystyle b nbsp sind folgende Sprachen Beispiele fur kontextfreie Sprachen L 1 a n b n n N displaystyle L 1 a n b n mid n in mathbb N nbsp L 2 v v R v besteht aus beliebig vielen a s und b s displaystyle L 2 vv text R mid v text besteht aus beliebig vielen a text s und b text s nbsp Die Sprache L 1 displaystyle L 1 nbsp enthalt die Worter a b displaystyle ab nbsp a a b b displaystyle aabb nbsp a a a b b b displaystyle aaabbb nbsp usw also immer so viele a displaystyle a nbsp s wie b displaystyle b nbsp s Wahlt man statt a displaystyle a nbsp und b displaystyle b nbsp die Symbole displaystyle nbsp und displaystyle nbsp entspricht das der korrekt verschachtelten Klammerung etwa displaystyle nbsp oder displaystyle nbsp Die Sprache L 2 displaystyle L 2 nbsp enthalt die Worter a a displaystyle aa nbsp a b b a displaystyle abba nbsp a b a a b a displaystyle abaaba nbsp a b b b b a displaystyle abbbba nbsp usw also alle symmetrischen Worter Da sie von vorne und hinten gelesen das gleiche Wort ergeben sind es Palindrome Die Sprache L 3 a n b n c n n N displaystyle L 3 a n b n c n mid n in mathbb N nbsp ist kontextsensitiv aber nicht kontextfrei Kontextfreie Sprachen finden in der Definition der Syntax von Programmiersprachen Anwendung es lassen sich zum Beispiel arithmetische Ausdrucke und allgemein korrekte Klammerstrukturen festlegen Grenzen der kontextfreien Sprachen liegen bei kontextrelevanten Eigenschaften wie z B der Typuberprufung in Programmiersprachen die sich nur durch kontextsensitive Grammatiken darstellen lassen In der Praxis verwendet man aber kontextfreie Parser mit zusatzlichen Funktionen und Datenstrukturen In der Computerlinguistik werden mit kontextfreien Grammatiken naturliche Sprachen nachgebildet Besteht ein Alphabet aus Wortern einer Sprache zum Beispiel d e r B a u m S a t z displaystyle der Baum Satz nbsp kann man mit wenigen Regeln einfache Nominalphrasen konstruieren Durch die Regeln N P d e r N displaystyle NP rightarrow der N nbsp und N B a u m S a t z displaystyle N rightarrow Baum mid Satz nbsp sind d e r B a u m displaystyle der Baum nbsp und d e r S a t z displaystyle der Satz nbsp korrekte Ausdrucke in der Grammatik Eigenschaften BearbeitenDie Klasse der kontextfreien Sprachen ist abgeschlossen unter der Vereinigung Spiegelung Konkatenation Verkettung kleeneschen Hullenbildung Anwendung von Homomorphismen Inverser Anwendung von Homomorphismen Durchschnittbildung mit regularen SprachenSie ist nicht abgeschlossen unter Durchschnitt Gegenbeispiel Die Sprachen L a n b n c m n m N 0 displaystyle L a n b n c m mid n m in mathbb N 0 nbsp und L a m b n c n n m N 0 displaystyle L a m b n c n mid n m in mathbb N 0 nbsp sind kontextfrei Aber L L a n b n c n n N 0 displaystyle L cap L a n b n c n mid n in mathbb N 0 nbsp ist nicht kontextfrei Komplement Widerspruchsbeweis Es wurde bereits gezeigt dass es kontextfreie Sprachen L 1 L 2 displaystyle L 1 L 2 nbsp gibt deren Schnitt L 1 L 2 displaystyle L 1 cap L 2 nbsp nicht kontextfrei ist Seien kontextfreie Sprachen unter Komplementbildung abgeschlossen Dann sind auch L 1 L 2 displaystyle overline L 1 overline L 2 nbsp kontextfrei Wegen der Abgeschlossenheit unter Vereinigung und De Morgan folgt dass L 1 L 2 displaystyle overline L 1 cup overline L 2 nbsp und damit L 1 L 2 L 1 L 2 displaystyle overline overline L 1 cup overline L 2 L 1 cap L 2 nbsp kontextfrei ist Widerspruch der Durchschnitt L 1 L 2 displaystyle L 1 cap L 2 nbsp wurde als nicht kontextfrei vorausgesetzt Anwendung von logarithmisch platzbeschrankter Reduktion Symmetrischer DifferenzDer Abschluss unter Vereinigung lasst sich durch Konstruktion einer neuen wiederum kontextfreien Grammatik nachweisen Seien G 1 N 1 T 1 P 1 S 1 displaystyle G 1 N 1 T 1 Pi 1 S 1 nbsp und G 2 N 2 T 2 P 2 S 2 displaystyle G 2 N 2 T 2 Pi 2 S 2 nbsp kontextfrei Neues Startsymbol S displaystyle S nbsp und neue Produktion S S 1 S 2 displaystyle S S 1 S 2 nbsp L G 1 L G 2 L G displaystyle Rightarrow L G 1 cup L G 2 L G nbsp mit G N 1 N 2 S T 1 T 2 S S 1 S 2 P 1 P 2 S 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 nbsp Genauso kann man fur zwei kontextfreie Sprachen die Abgeschlossenheit unter Konkatenation zeigen Seien G 1 N 1 T 1 P 1 S 1 displaystyle G 1 N 1 T 1 Pi 1 S 1 nbsp und G 2 N 2 T 2 P 2 S 2 displaystyle G 2 N 2 T 2 Pi 2 S 2 nbsp kontextfrei Neues Startsymbol S displaystyle S nbsp und neue Produktion S S 1 S 2 displaystyle S S 1 S 2 nbsp L G 1 L G 2 L G displaystyle Rightarrow L G 1 L G 2 L G nbsp mit G N 1 N 2 S T 1 T 2 S S 1 S 2 P 1 P 2 S 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 nbsp Auch die Anwendung von Kleene entspricht einer neuen kontextfreien Grammatik Sei G N T P S displaystyle G N T Pi S nbsp kontextfrei Neues Startsymbol S neu displaystyle S text neu nbsp und neue Produktion S neu S neu S displaystyle S text neu S text neu S nbsp L G L G 1 displaystyle Rightarrow L G L G 1 nbsp mit G 1 N S neu T S neu S neu S ϵ P S neu displaystyle G 1 N cup S text neu T S text neu S text neu S epsilon cup Pi S text neu nbsp Jede regulare Sprache ist auch kontextfrei da jede regulare Grammatik auch eine kontextfreie Grammatik ist Es existieren kontextsensitive Sprachen die nicht kontextfrei sind Ein solches Beispiel ist a n b n c n n N 0 displaystyle a n b n c n mid n in mathbb N 0 nbsp Pumping Lemmas existieren jeweils in verschiedenen Varianten fur regulare und kontextfreie Sprachen Fur kontextfreie Sprachen beschreiben sie notwendige aber nicht hinreichende Eigenschaften Der Nachweis dass eine formale Sprachen nicht kontextfrei ist wird in der Regel uber die Verletzung dieser notwendigen Eigenschaften gefuhrt Oft wird die untersuchte Sprache zunachst durch den Schnitt mit einer regularen Sprache geeignet ausgedunnt Dieses Vorgehen ist durch den oben genannten Abschluss unter Schnitt mit regularen Sprachen gerechtfertigt Ein offenes Problem ist die Frage ob die Menge der primitiven Worter kontextfrei ist 1 Dabei ist ein Wort uber einem beliebigen Alphabet primitiv wenn es keine Wiederholung eines anderen Wortes ist also nicht die Form w n displaystyle w n nbsp fur ein beliebiges anderes nicht leeres Wort w displaystyle w nbsp desselben Alphabetes und ein ganzzahliges n 2 displaystyle n geq 2 nbsp hat 2 Typische Entscheidungsprobleme BearbeitenSeien L displaystyle L nbsp L 1 displaystyle L 1 nbsp und L 2 displaystyle L 2 nbsp gegebene kontextfreie Sprachen uber dem Alphabet S displaystyle Sigma nbsp Dann ergeben sich folgende typische Problemstellungen Wortproblem Gehort ein Wort w S displaystyle w in Sigma nbsp zu L displaystyle L nbsp Leerheitsproblem Ist L displaystyle L nbsp die leere Menge Endlichkeitsproblem Ist L displaystyle L nbsp eine endliche Menge von Wortern L lt displaystyle left L right lt infty nbsp Die oben aufgezahlten Probleme sind bei kontextfreien Sprachen entscheidbar das Wortproblem durch den Cocke Younger Kasami Algorithmus Das Aquivalenzproblem L 1 L 2 displaystyle L 1 L 2 nbsp ist ab einschliesslich dieser Stufe der Chomsky Hierarchie nicht mehr entscheidbar Weitergehende Eigenschaften BearbeitenDLIN displaystyle subsetneq nbsp DCFL displaystyle subsetneq nbsp CFL displaystyle subsetneq nbsp GCSL displaystyle subsetneq nbsp CSL REG displaystyle subsetneq nbsp DLIN displaystyle subsetneq nbsp LIN displaystyle subsetneq nbsp CFL Fur jedes n N displaystyle n in mathbb N nbsp gibt es Sprachen die sich als Schnitt von n displaystyle n nbsp kontextfreien Sprachen darstellen lassen aber nicht als Schnitt von n 1 displaystyle n 1 nbsp kontextfreien Sprachen Naturliche Sprache BearbeitenIn der Linguistik werden kontextfreie Grammatiken auch zur Beschreibung der Syntax naturlicher Sprachen eingesetzt Es wurde aber zum Beispiel fur das Schweizerdeutsch nachgewiesen dass die Sprache sich nicht vollstandig mit einer solchen Grammatik beschreiben lasst 3 Vielfach werden aber in der Computerlinguistik kontextfreie Grammatiken oder aquivalente Formalismen mit zusatzlichen Datenstrukturen auch fur Sprachen wie Schweizerdeutsch verwendet Siehe auch BearbeitenBackus Naur Form eine kompakte formale Metasprache zur Darstellung kontextfreier GrammatikenLiteratur BearbeitenUwe Schoning 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 Einfuhrung in die Automatentheorie Formale Sprachen und Komplexitatstheorie 2 uberarbeitete Auflage Pearson Studium Munchen 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 BearbeitenCFL In Complexity Zoo englisch Einzelnachweise Bearbeiten Pal Domosi 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 Context Free Languages and Primitive Words siehe oben S 11 Vorschau auf Google Books abgerufen am 30 November 2015 Stuart M Shieber Evidence against the context freeness of natural language In Linguistics and Philosophy 8 1985 pdf 6 3 MB Abgerufen von https de wikipedia org w index php title Kontextfreie Sprache amp oldid 236502910