Context sensitive language

from Wikipedia, the free encyclopedia

The context-sensitive languages (English context-sensitive languages , abbreviated to CSL ) are a class of formal languages , a sub-area of theoretical computer science . The class CSL corresponds to the class of the type 1 languages ​​from the Chomsky hierarchy .


A formal language is context-sensitive if and only if there is a context-sensitive grammar that generates this language. A context-sensitive grammar is one that in every rule always replaces a nonterminal in a context into a non-empty sequence of characters (nonterminal or terminal). The monotonous grammars are equivalent to the context-sensitive ones, they characterize the context-sensitive languages. A grammar is called monotonic if all of its rules have the property that the right side of each rule is at least as long as its left side.


The class of context-sensitive languages ​​corresponds to the class of languages ​​accepted by nondeterministic linearly bounded automata . The CSL class thus represents the complexity class of languages ​​that can be accepted by a nondeterministic Turing machine ( NSPACE (n) ) in a linearly restricted space and is also one of the PSPACE -complete problems.

The class of context-sensitive languages ​​is completed under

The class of context-sensitive languages ​​is not completed under

It is not known whether the class can already be accepted by deterministic Turing machines with linear space constraints. (This problem is known as Kuroda's problem or 1st LBA problem.)

Since the derivatives are never shorter, ( word problem ), with L, context-sensitive language, can be decided .


The following language is a typical example of CSL:

is context sensitive, but not context free .

Individual evidence

  1. ^ Uwe Schöning : Theoretical Computer Science - in short . 4th edition. Spektrum Akademischer Verlag, Berlin 2001, ISBN 3-8274-1099-1 , p. 58 .