https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Kontextsensitive_SpracheKontextsensitive Sprache - Versionsgeschichte2026-05-27T10:32:23ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Kontextsensitive_Sprache&diff=397111&oldid=previmported>FlMcc: /* growthexperiments-addlink-summary-summary:2|0|0 */2024-12-05T05:55:17Z<p><span class="autocomment">growthexperiments-addlink-summary-summary:2|0|0</span></p>
<p><b>Neue Seite</b></p><div>Die '''kontextsensitiven Sprachen''' (englisch ''{{lang|en|context-sensitive languages}}'', abgekürzt durch ''CSL'') sind eine Klasse der [[Formale Sprache|formalen Sprachen]], einem Teilgebiet der [[Theoretische Informatik|Theoretischen Informatik]]. Die Klasse CSL entspricht der Klasse der Typ-1-Sprachen aus der [[Chomsky-Hierarchie]].<br />
<br />
== Definition ==<br />
Eine formale Sprache ist genau dann ''kontextsensitiv,'' wenn eine [[kontextsensitive Grammatik]] existiert, die diese Sprache erzeugt.<br />
Eine ''kontextsensitive Grammatik'' ist eine, die in jeder Regel immer ein Nichtterminal in einem Kontext in eine nichtleere Folge von Zeichen (Nichtterminale oder Terminale) ersetzt. Die [[Monotone Grammatik|monotonen Grammatiken]] sind den kontextsensitiven äquivalent, sie charakterisieren die kontextsensitiven Sprachen. Eine Grammatik heißt ''monoton,'' wenn alle ihre Regeln die Eigenschaft haben, dass die rechte Seite einer jeden Regel mindestens so lang ist wie deren linke Seite.<br />
<br />
== Eigenschaften ==<br />
Die Klasse der kontextsensitiven Sprachen entspricht der Klasse der von [[Nichtdeterminismus|nichtdeterministischen]] [[Linear beschränkte Turingmaschine|linear beschränkten Automaten]] akzeptierten Sprachen. Damit repräsentiert die Klasse CSL die [[Komplexitätsklasse]] der Sprachen, die auf linear beschränktem Platz von einer [[Nichtdeterministische Turingmaschine|nichtdeterministischen Turingmaschine]] ([[NSPACE|NSPACE(n)]]) akzeptiert werden können und zählt außerdem zu den [[PSPACE]]-vollständigen Problemen.<br />
<br />
Die Klasse der kontextsensitiven Sprachen ist '''[[Abgeschlossenheit (algebraische Struktur)|abgeschlossen]]''' unter<br />
* [[Vereinigungsmenge|Vereinigung]], <br />
* [[Konkatenation (Formale Sprache)|Konkatenation]],<br />
* [[Komplement (Mengenlehre)|Komplementbildung]],<br />
* [[Schnittmenge|Durchschnitt]],<br />
* [[Kleenesche Hülle|Kleene-Operation *]],<br />
* inversen [[Homomorphismus|Homomorphismen]],<br />
* <math>\varepsilon</math>-freien Homomorphismen,<br />
* [[Logarithmisch_platzbeschränkte_Reduktion|logarithmisch platzbeschränkter Reduktion]].<br />
<br />
Die Klasse der kontextsensitiven Sprachen ist '''nicht abgeschlossen''' unter<br />
* löschenden Homomorphismen,<br />
* [[Polynomialzeitreduktion|polynomiell zeitbeschränkter Reduktion]].<br />
<br />
Es ist nicht bekannt, ob die Klasse bereits von deterministischen Turingmaschinen mit linearer Platzbeschränkung akzeptiert werden kann. (Dieses Problem ist unter Namen [[Kurodas Problem]] oder 1. LBA-Problem bekannt.)<br />
<br />
Da die Ableitungen niemals kürzer werden, ist auch <math>x \in L</math> ([[Wortproblem (Berechenbarkeitstheorie)|Wortproblem]]), mit L kontextsensitive Sprache, [[Entscheidbarkeit|entscheidbar]].<br />
<br />
== Beispiele ==<br />
Die folgende Sprache ist ein typisches Beispiel für CSL:<br />
: <math>\mbox{count}_3:=\{a^nb^nc^n\mid n\in\mathbb{N}\}</math><br />
<math>\mbox{count}_3</math> ist kontextsensitiv, aber nicht [[Kontextfreie Sprache|kontextfrei]].<ref>{{Literatur | Autor=[[Uwe Schöning]] | Auflage=4. | Titel=Theoretische Informatik – kurzgefasst | Jahr=2001 | Verlag=Spektrum Akademischer Verlag | Ort= Berlin | ISBN=3-8274-1099-1 | Seiten=58}}</ref><br />
<br />
== Einzelnachweise ==<br />
<references/><br />
<br />
[[Kategorie:Komplexitätstheorie]]<br />
[[Kategorie:Theorie formaler Sprachen]]</div>imported>FlMcc