| Context-sensitive Language |
Article Index for Context-sensitive |
Website Links For Language |
Information AboutContext-sensitive Language |
| CATEGORIES ABOUT CONTEXT-SENSITIVE LANGUAGE | |
| formal languages | |
|
COMPUTATIONAL PROPERTIES Computationally the context-sensitive languages are equivalent with linear bounded non-deterministic Turing Machine s. 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. 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. PROPERTIES OF CONTEXT-SENSITIVE LANGUAGES
SEE ALSO
|
|
|