imported>Phzh: Form, typo

2026-03-25T06:07:13Z

Form, typo

Neue Seite

Die '''kontextsensitiven Grammatiken''' (kurz ''CSG'', von engl. {{lang|en|context-sensitive grammar}}) sind eine Klasse [[Formale Grammatik|formaler Grammatiken]] und identisch mit den ''Typ-1''-Grammatiken der [[Chomsky-Hierarchie]]. Sie zeichnen sich dadurch aus, dass einzelne [[Nichtterminalsymbol]]e nur in einem vorgegebenen Kontext ersetzt werden dürfen.

== Definition ==
Eine kontextsensitive Grammatik ist eine [[formale Grammatik]] <math>G=(V,T,P,S)</math> mit
* einer endlichen Menge <math>V</math> (Vokabular),
* Terminalsymbolen <math>T \subset V</math>
* Nichtterminalsymbolen <math>N = V \setminus T</math>, darunter das
* Startsymbol <math>S \in N</math>
* [[Produktionsregel]]n <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 V^*</math>
** <math>X \in N</math>
** <math>\gamma \in V^+</math>
** <math>S</math> kommt auf keiner rechten Seite einer Produktionsregel vor.

Manche Autoren bezeichnen alternativ das Quadrupel <math>(N, T, P, S)</math> als Grammatik <math>G</math>.

=== 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 [[Leeres Wort|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.
Durch das Hinzufügen des leeren Wortes wird erreicht, dass die kontextsensitiven Sprachen eine echte Obermenge der kontextfreien Sprachen sind. Ansonsten hätte man als Resultat die umständlicher zu beschreibende Situation, dass nur die kontextfreien Grammatiken ''ohne leere-Wort-Produktionen'' auch kontextsensitive Grammatiken sind.

=== Kontextsensitive und monotone Grammatiken ===
Die Produktionsregeln kontextsensitiver Grammatiken verkürzen die linke Seite nicht. Bis auf die Ausnahmeregel <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 (bis auf die genannte leere-Wort-Produktion) immer auch eine [[monotone Grammatik]]. Kontextsensitive und monotone Grammatiken erzeugen aber die gleiche Sprach[[Klasse (Mengentheorie)|klasse]].

Einige Autoren definieren kontextsensitive Grammatiken im Sinne monotoner Grammatiken<ref>zum Beispiel {{Literatur |Autor=[[Uwe Schöning]] |Titel=Theoretische Informatik – kurz gefasst |Auflage=5. |Verlag=Spektrum Akademischer Verlag |Datum=2008 |ISBN=978-3-8274-1824-1 |Kapitel=Abschnitt 1.1.2 |Seiten=9}}</ref>. Die Produktionsregeln der Form <math>\alpha X\beta \rightarrow \alpha\gamma\beta</math> werden gelegentlich nur als typische oder kanonische Form kontextsensitiver Regeln betrachtet,<ref>{{Literatur |Autor=Klaus W. Wagner |Titel=Theoretische Informatik: Eine kompakte Einführung |Verlag=Springer |Datum=2003 |ISBN=3-540-01313-X |Kapitel=Kapitel 6 |Seiten=187 |Online={{Google Buch |BuchID=3uc-golkGC0C |Seite=187}}}}</ref> im Gegensatz zu <math>S\rightarrow\varepsilon</math>.

=== 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.<ref>M. Penttonen, ''One-Sided and Two-Sided Context in Formal Grammars'', Information and Control, 25 (1974), 371–392</ref><ref>siehe auch Rozenberg und Salomaa, ''Handbook of Formal Languages.'' S. 190.</ref>

=== Alternative Notation ===
Im Bereich der [[Sprachwissenschaft]]en findet man eine alternative Notation der Produktionsregeln<ref>{{Literatur |Autor=Daniel Jurafsky, James H. Martin |Titel=Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition |Verlag=Prentice Hall |Datum=2009 |ISBN=978-0-13-187321-6 |Kapitel=Kapitel 16 |Seiten=531 |Online={{Google Buch |BuchID=fZmj5UNK8AQC |Seite=531}}}}</ref>. 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 [[Kontextsensitive Sprache|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 [[Determinismus|nichtdeterministischen]], [[Linear beschränkte Turingmaschine|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 (Berechenbarkeitstheorie)|Wortproblem]] (die Frage, ob <math>x \in L</math> gilt) für kontextsensitive Sprachen <math>L</math> [[Entscheidbarkeit|entscheidbar]].

== Literatur ==
* {{Literatur
|Autor=Grzegorz Rozenberg, Arto Salomaa
|Titel=Handbook of Formal Languages. ''Volume 1:'' Word, Language, Grammar
|Verlag=Springer
|Ort=Berlin u. a.
|Datum=1997
|ISBN=3-540-60420-0
|Online={{Google Buch |BuchID=yQ59ojndUt4C}}}}
* {{Literatur
|Autor=Katrin Erk, Lutz Priese
|Titel=Theoretische Informatik: Eine umfassende Einführung
|Auflage=3., erweiterte
|Verlag=Springer
|Ort=Berlin u. a.
|Datum=2008
|ISBN=978-3-540-76319-2
|Online={{Google Buch |BuchID=WDeSCvLELE4C}}}}

== Einzelnachweise ==
<references />

[[Kategorie:Theorie formaler Sprachen]]

Kontextsensitive Grammatik - Versionsgeschichte

imported>Phzh: Form, typo