In theoretical computer science, 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.
Computationally, a context-sensitive language is equivalent with a linear bounded nondeterministic Turing machine, also called a linear bounded automaton. That is a non-determ...
more
In theoretical computer science, 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.
Computationally, a context-sensitive language is equivalent with a linear bounded nondeterministic Turing machine, also called a linear bounded automaton. 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...
less
