In der theoretischen Informatik ist eine mit dem Zusammenhang empfindliche Sprache eine formelle Sprache, die durch eine mit dem Zusammenhang empfindliche Grammatik definiert werden kann. Das ist einer der vier Typen von Grammatiken in der Hierarchie von Chomsky. Der vier ist das am wenigsten häufig verwendet, sowohl in der Theorie als auch in Praxis.

Rechenbetonte Eigenschaften

Rechenbetont ist eine mit dem Zusammenhang empfindliche Sprache mit einer geradlinigen begrenzten nichtdeterministischen Maschine von Turing, auch genannt einen geradlinigen begrenzten Automaten gleichwertig. Das ist eine nichtdeterministische Maschine von Turing mit einem Band nur kn Zellen, wo n die Größe des Eingangs ist und k eine mit der Maschine vereinigte Konstante ist. Das bedeutet, dass jede formelle Sprache, die durch solch eine Maschine entschieden werden kann, eine mit dem Zusammenhang empfindliche Sprache ist, und jede mit dem Zusammenhang empfindliche Sprache durch solch eine Maschine entschieden werden kann.

Dieser Satz von Sprachen ist auch bekannt als NLIN-RAUM, weil sie mit dem geradlinigen Raum auf einer nichtdeterministischen Maschine von Turing akzeptiert werden können. Der Klassen-LIN-RAUM wird dasselbe definiert, außer dem Verwenden einer deterministischen Maschine von Turing. Klar ist LIN-RAUM eine Teilmenge des NLIN-RAUMS, aber es ist ob LIN-SPACE=NLIN-SPACE nicht bekannt. Es wird weit vermutet, dass sie nicht gleich sind.

Beispiele

Ein Beispiel einer mit dem Zusammenhang empfindlichen Sprache, die nicht ohne Zusammenhänge ist, ist L = {a: P ist eine Primzahl}. Wie man zeigen Kann, ist L eine mit dem Zusammenhang empfindliche Sprache durch das Konstruieren eines geradlinigen begrenzten Automaten, der L akzeptiert. Wie man leicht zeigen kann, ist die Sprache weder regelmäßig noch freier Zusammenhang, indem sie an die jeweiligen pumpenden Lemmata wegen jeder der Sprachklassen zu L gewandt wird.

Ein Beispiel der rekursiven Sprache, die nicht mit dem Zusammenhang empfindlich ist, ist jede rekursive Sprache, deren Entscheidung ein EXPSPACE-hartes Problem, sagen wir, der Satz von Paaren von gleichwertigen regelmäßigen Ausdrücken mit exponentiation ist.

Eigenschaften von mit dem Zusammenhang empfindlichen Sprachen

• Die Vereinigung, die Kreuzung, die Verkettung und der kleene Stern von zwei mit dem Zusammenhang empfindlichen Sprachen sind mit dem Zusammenhang empfindlich.
• Die Ergänzung einer mit dem Zusammenhang empfindlichen Sprache ist selbst mit dem Zusammenhang empfindlich.
• Jede Sprache ohne Zusammenhänge ist mit dem Zusammenhang empfindlich.
• Die Mitgliedschaft einer Schnur auf einer Sprache, die durch eine willkürliche mit dem Zusammenhang empfindliche Grammatik, oder durch eine willkürliche deterministische mit dem Zusammenhang empfindliche Grammatik definiert ist, ist ein PSPACE-ganzes Problem.

Siehe auch

• Geradliniger begrenzter Automat

Hierarchie von Chomsky

• Das Nichtzusammenziehen von Grammatiken - erzeugt genau die mit dem Zusammenhang empfindlichen Sprachen
• Mit einem Inhaltsverzeichnis versehene Sprachen - eine strenge Teilmenge der mit dem Zusammenhang empfindlichen Sprachen
• Sipser, M. (1996), Einführung in die Theorie der Berechnung, PWS Publishing Co.