Kontextsensitive Grammatik - LinkFang.de





Kontextsensitive Grammatik


Die kontextsensitiven Grammatiken (kurz CSG, von engl. context-sensitive grammar) sind eine Klasse formaler Grammatiken und identisch mit den Typ-1-Grammatiken der Chomsky-Hierarchie. Sie zeichnen sich dadurch aus, dass einzelne Nichtterminalsymbole nur in einem vorgegebenen Kontext ersetzt werden dürfen.

Definition

Eine kontextsensitive Grammatik ist eine formale Grammatik [math]G=(N,T,P,S)[/math] mit

  • Nichtterminalsymbolen [math]N[/math]
  • Terminalsymbolen [math]T[/math]
  • Startsymbol [math]S \in N[/math]
  • Produktionsregeln [math]P[/math] der Form [math]\alpha X\beta \rightarrow \alpha\gamma\beta[/math] oder der Form [math]S \rightarrow \varepsilon[/math], wenn gilt:
    • [math]\alpha, \beta \in (N \cup T)^*[/math]
    • [math]X \in N[/math]
    • [math]\gamma \in (N \cup T)^+[/math]
    • [math]S[/math] kommt auf keiner rechten Seite einer Produktionsregel vor

Beschreibung

Bis auf eine Ausnahme hat jede Produktionsregel der Definition nach die Form [math]\alpha X \beta \rightarrow \alpha\gamma\beta [/math] und [math]\gamma \neq \varepsilon[/math].

Das bedeutet, dass das Nichtterminalsymbol [math]X[/math] im Kontext der Zeichenketten [math]\alpha[/math] und [math]\beta[/math] durch [math]\gamma[/math] ersetzt wird. Aber während [math]\gamma[/math] aus mindestens einem Symbol (Terminal- oder Nichtterminalsymbol) bestehen muss, kann sowohl [math]\alpha[/math] als auch [math]\beta[/math] leer sein. Folgende Sonderfälle sind daher gemäß der Definition möglich:

  • [math]\alpha X \rightarrow \alpha\gamma[/math]
  • [math]X\beta \rightarrow \gamma\beta[/math]
  • [math]X \rightarrow \gamma[/math]

Um das leere Wort [math]\varepsilon[/math] erzeugen zu können, erlaubt man die Regel [math]S \rightarrow \varepsilon[/math], sofern [math]S[/math] auf keiner rechten Seite einer Produktionsregel vorhanden ist.

Kontextsensitive und monotone Grammatiken

Die Produktionsregeln kontextsensitiver Grammatiken verkürzen die linke Seite nicht. Bis auf die Regel [math]S\rightarrow\varepsilon[/math] erfüllen also alle Regeln [math]w_1\rightarrow w_2[/math] die Bedingung [math]\left|w_1\right| \leq \left|w_2\right|[/math]. Eine kontextsensitive Grammatik ist deshalb immer auch eine monotone Grammatik. Kontextsensitive und monotone Grammatiken erzeugen aber die gleiche Sprachklasse.

Einige Autoren definieren kontextsensitive Grammatiken im Sinne monotoner Grammatiken[1]. Die Produktionsregeln der Form [math]\alpha X\beta \rightarrow \alpha\gamma\beta[/math] werden gelegentlich nur als typische oder kanonische Form kontextsensitiver Regeln betrachtet[2].

Normalformen

Zu jeder kontextsensitiven Grammatik existiert eine Grammatik in Kuroda-Normalform mit Produktionsregeln der Form

  • [math]A \rightarrow a[/math]
  • [math]A \rightarrow B[/math]
  • [math]A \rightarrow BC[/math]
  • [math]AB \rightarrow CD[/math]

Eine Grammatik in Kuroda-Normalform ist im Allgemeinen zwar monoton aber nicht mehr kontextsensitiv.

Eine kontextsensitive Normalform ist die einseitige Normalform mit Regeln der Art:

  • [math]A \rightarrow a[/math]
  • [math]A \rightarrow BC[/math]
  • [math]AB \rightarrow AC[/math]

Zu jeder kontextsensitiven Grammatik gibt es eine Grammatik in einseitiger Normalform[3][4].

Alternative Notation

Im Bereich der Sprachwissenschaften findet man eine alternative Notation der Produktionsregeln[5]. Man gibt die Ersetzungsregeln ähnlich wie bei kontextfreien Regeln an und nennt den Kontext, in dem die Regel angewendet werden darf, am rechten Ende der Regel: [math]X \rightarrow \gamma \; / \alpha\_\!\_\!\_\!\_\beta /[/math]

Von kontextsensitiven Grammatiken erzeugte Sprachen

Mit Hilfe kontextsensitiver Grammatiken lassen sich genau die kontextsensitiven Sprachen erzeugen. Das heißt: Jede kontextsensitive Grammatik erzeugt eine kontextsensitive Sprache und zu jeder kontextsensitiven Sprache existiert eine kontextsensitive Grammatik, die diese Sprache erzeugt.

Die kontextsensitiven Sprachen sind genau die Sprachen, die von einer nichtdeterministischen, linear beschränkten Turingmaschine erkannt werden können; d.h. von einer nichtdeterministischen Turing-Maschine, deren Band linear durch die Länge der Eingabe beschränkt ist (d.h. es gibt eine konstante Zahl [math]a[/math] so dass das Band der Turing-Maschine höchstens [math]a \cdot x[/math] Felder besitzt, wobei [math]x[/math] die Länge des Eingabewortes ist).

Darum ist auch das Wortproblem (die Frage, ob [math]x \in L[/math] gilt) für kontextsensitive Sprachen [math]L[/math] entscheidbar.

Einzelnachweise

  1. zum Beispiel Uwe Schöning: Theoretische Informatik – kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, 2008, ISBN 978-3-8274-1824-1, Abschnitt 1.1.2, S. 9.
  2. Klaus W. Wagner: Theoretische Informatik: Eine kompakte Einführung. Springer, 2003, ISBN 978-3-540-01313-6, Kapitel 6, S. 187 (eingeschränkte Vorschau in der Google-Buchsuche).
  3. M. Penttonen, One-Sided and Two-Sided Context in Formal Grammars, Information and Control, 25 (1974), 371-392
  4. siehe auch Rozenberg und Salomaa, Handbook of Formal Languages, S.190
  5. Daniel Jurafsky, James H. Martin: Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Prentice Hall, 2009, ISBN 978-0-13-187321-6, Kapitel 16, S. 531 (eingeschränkte Vorschau in der Google-Buchsuche).

Literatur


Kategorien: Theorie formaler Sprachen

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Kontextsensitive Grammatik (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.