ExamplesEvery context-free language is context-sensitive. An example of a context-sensitive language that is not context-free is L = { an : n is a prime number }. The easiest way to show this is using a linear bounded Turing machine. |
Computationally the context-sensitive lanugages are equivalent with linear bounded Turing machines where a linear bounded Turing machine is a Turing with a tape of only kn cells where n is the size of the input and k 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.
Every context-free language is context-sensitive.
An example of a context-sensitive language that is not context-free is L = { an : n is a prime number }. The easiest way to show this is using a linear bounded Turing machine.