Context sensitive language

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 .

definition

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.

properties

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

Association ,
Concatenation ,
Complement formation ,
Average ,
Kleene operation * ,
inverse homomorphisms ,
${\ displaystyle \ varepsilon}$ -free homomorphisms,
logarithmic space-constrained reduction .

The class of context-sensitive languages is not completed under

deleting homomorphisms,
polynomial time-bounded reduction .

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 . ${\ displaystyle x \ in L}$

Examples

The following language is a typical example of CSL:

{\ displaystyle {\ mbox {count}} _ {3}: = \ {a ^ {n} b ^ {n} c ^ {n} \ mid n \ in \ mathbb {N} \}}

${\ displaystyle {\ mbox {count}} _ {3}}$ is context sensitive, but not context free .

Individual evidence

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

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