Context-sensitive language
From Wikipedia, the free encyclopedia
A context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy. Of the four, this is the least often used, in both theory and practice.
Contents |
[edit] Computational properties
Computationally the context-sensitive languages are equivalent with linear bounded non-deterministic Turing machines. That is a non-deterministic Turing machine with a tape of only kn cells, where n is the size of the input and k is a constant associated with the machine. This means that every formal language that can be decided by such a machine is a context-sensitive language, and every context-sensitive language can be decided by such a machine.
This set of languages is also known as NLIN-SPACE, because they can be accepted using linear space on a non-deterministic Turing machine. The class LIN-SPACE is defined the same, except using a deterministic Turing machine. Clearly LIN-SPACE is a subset of NLIN-SPACE, but it is not known whether LIN-SPACE=NLIN-SPACE. It is widely suspected they are not equal.
[edit] Examples
An example of a context-sensitive language that is not context-free is L = { ap : p is a prime number }. The easiest way to show this is using a linear bounded Turing machine.
[edit] Properties of context-sensitive languages
- The union, intersection, and concatenation of two context-sensitive languages is context-sensitive.
- The complement of a context-sensitive language is itself context-sensitive.
- Every context-free language is context-sensitive.
[edit] See also
- Chomsky hierarchy
- Tree-adjoining grammars—generate a strict subset of the context-sensitive language
| Automata theory: formal languages and formal grammars | |||
|---|---|---|---|
| Chomsky hierarchy |
Grammars | Languages | Minimal automaton |
| Type-0 | Unrestricted | Recursively enumerable | Turing machine |
| n/a | (no common name) | Recursive | Decider |
| Type-1 | Context-sensitive | Context-sensitive | Linear-bounded |
| n/a | Indexed | Indexed | Nested stack |
| Type-2 | Context-free | Context-free | Nondeterministic Pushdown |
| n/a | Deterministic Context-free | Deterministic Context-free | Deterministic Pushdown |
| Type-3 | Regular | Regular | Finite |
| Each category of languages or grammars is a proper subset of the category directly above it. | |||
