Kontextsensitive Grammatik

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.

Inhaltsverzeichnis

Definition

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

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

Beschreibung

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

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

  • \alpha X \rightarrow \alpha\gamma
  • X\beta \rightarrow \gamma\beta
  • X \rightarrow \gamma

Um das leere Wort ε erzeugen zu können, erlaubt man die Regel S \rightarrow \varepsilon, sofern S 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 S\rightarrow\varepsilon erfüllen also alle Regeln w_1\rightarrow w_2 die Bedingung \left|w_1\right| \leq \left|w_2\right|. 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 \alpha X\beta \rightarrow \alpha\gamma\beta werden gelegentlich nur als typische oder kanonische Form kontextsensitiver Regeln betrachtetl[2].

Normalformen

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

  • A \rightarrow a
  • A \rightarrow B
  • A \rightarrow BC
  • AB \rightarrow CD

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:

  • A \rightarrow a
  • A \rightarrow BC
  • AB \rightarrow AC

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

Alternative Notation

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

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 a so dass das Band der Turing-Maschine höchstens a \cdot x Felder besitzt, wobei x die Länge des Eingabewortes ist).

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

Beispiel

Die kontextsensitive Sprache L = \{a^nb^nc^n|n\geq 1\} der Wörter, die aus genauso vielen a wie folgenden b und genauso vielen folgenden c besteht, wird durch folgende kontextsensitive Grammatik erzeugt[5]:

G = (N,T,P,S) mit Terminalsymbolen T = {a,b,c} und Nicht-Terminalen N = {B,C,H,S} sowie den Produktionsregeln P:

  1. S \rightarrow aSBC \mid aBC
  2. CB \rightarrow HB
  3. HB \rightarrow HC
  4. HC \rightarrow BC
  5. aB \rightarrow ab
  6. bB \rightarrow bb
  7. bC \rightarrow bc
  8. cC \rightarrow cc


Das Wort aabbcc \in L lässt sich dann folgendermaßen erzeugen (der jeweils im nächsten Schritt ersetzte Kontext ist unterstrichen):

\begin{array}{l}\underline{S} \Rightarrow_1 a\underline{S}BC \Rightarrow_1 aaB\underline{CB}C \Rightarrow_2 aaB\underline{HB}C \\ 
\Rightarrow_3 aaB\underline{HC}C \Rightarrow_4 a\underline{aB}BCC \Rightarrow_5 aa\underline{bB}CC \\
\Rightarrow_6 aab\underline{bC}C \Rightarrow_7 aabb\underline{cC} \Rightarrow_8 aabbcc \end{array}

Einzelnachweise

  1. zum Beispiel Uwe Schöning: Theoretische Informatik – kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, 2008, ISBN 9783827418241, Abschnitt 1.1.2, S. 9.
  2. Klaus W. Wagner: Theoretische Informatik: Eine kompakte Einführung. Springer, 2003, ISBN 9783540013136, Kapitel 6, S. 187 (Eingeschränkte Vorschau in der Google Buchsuche).
  3. siehe Rozenberg und Salomaa, Handbook of Formal Languages, S.190
  4. Daniel Jurafsky, James H. Martin: Speech and Language Processing: An Introduction to Natural Languagae Processing, Computational Linguistics, and Speech Recognition. Prentice Hall, 2009, ISBN 9780131873216, Kapitel 16, S. 531 (Eingeschränkte Vorschau in der Google Buchsuche).
  5. J. C. Martin: Introduction to Languages and the Theory of Computation. 3. Auflage. McGraw-Hill, 2002.

Literatur


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kontextsensitive Sprache — Die kontextsensitiven Sprachen (englisch context sensitive languages, abgekürzt durch CSL) sind eine Klasse der formalen Sprachen, einem Teilgebiet der Theoretischen Informatik. Die Klasse CSL entspricht der Klasse der Typ 1 Sprachen aus der… …   Deutsch Wikipedia

  • Kontext-sensitive Grammatik — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Typ-0-Grammatik — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Kommunizierende Grammatik-Systeme — bestehen aus mehreren formalen Grammatiken, die über eine Möglichkeit verfügen, miteinander zu kommunizieren. Die Art der Kommunikation ist vom jeweiligen System abhängig und kann die generative Mächtigkeit der einzelnen Grammatiken erweitern.… …   Deutsch Wikipedia

  • Kommunizierendes Grammatik-System — Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf… …   Deutsch Wikipedia

  • Formale Grammatik — Formale Grammatiken sind mathematische Modelle von Grammatiken, die mit Hilfe des Semi Thue Systems angegeben werden und durch die formale Sprachen beschrieben und erzeugt werden können. Sie werden in der theoretischen Informatik, insbesondere in …   Deutsch Wikipedia

  • Wachsend kontextsensitive Sprache — Wachsend kontextsensitive Sprachen (engl.: Growing Context Sensitive Languages, abgekürzt: GCSL) sind ein Begriff aus der Theorie der Formalen Sprachen, einem Teilgebiet der Theoretischen Informatik. Eine wachsend kontextsensitive Sprache wird… …   Deutsch Wikipedia

  • Generative Grammatik — ist der Oberbegriff für Grammatik Modelle, mit deren Regelsystem sich die Sätze einer Sprache – im Gegensatz zu den ausschließlich die Phänomene beschreibenden Sprachlehren – generieren lassen (gebildet aus lat. generare = erzeugen und griech.… …   Deutsch Wikipedia

  • Chomsky-Hierarchie — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der Theoretischen Informatik. Sie ist eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Chomsky-Typ — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”