Context-sensitive language
The context-sensitive languages (English context - sensitive languages , abbreviated by CSL) are a class of formal languages , a branch of theoretical computer science. The class CSL corresponds to the class of type -1 languages from the Chomsky hierarchy.
Definition
A formal language is context-sensitive if and only if there exists 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 in a non-empty sequence of characters ( non-terminals or terminals ). The monotone grammars are equivalent to context-sensitive, they characterize the context-sensitive languages . A grammar is called monotonic if all its rules have the property that the right side of each rule is at least as long as the left side.
Properties
The class of context-sensitive languages corresponds to the class of language accepted by nondeterministic linear bounded automata languages. In order for the class CSL represents the complexity class of languages on linear space is limited by a non-deterministic Turing machine ( NSPACE ( n ) ) can be accepted, and also one of the PSPACE - complete problems.
The class of context-sensitive languages is closed under
- Association,
- Concatenation,
- Complementation,
- Average,
- Kleene * operation,
- Inverse homomorphisms,
- - free homomorphisms,
- Logarithmic space- limited reduction.
The class of context-sensitive languages is not closed under
- Delete homomorphisms,
- Polynomially time- limited reduction.
It is not known whether the class can be accepted by deterministic Turing machines with linear space limit already. ( This issue is under Kuroda's name problem or first LBA problem is known. )
Since the leads are never shorter, is also (word problem), with L context-sensitive language, decidable.
Examples
The following language is a typical example of CSL:
Is context-sensitive but not context-free.