Context-Sensitive Language

Overview

A linear bounded automaton (LBA) is a restricted type of Turing machine wherein the tape head isn't permitted to move off the portion of the tape containing the input. If the machine tries to move its head off either end of the input, the head stays where it is in the same way the head does nto move off the left-hand end of an ordinary Turing machine's tape.

Using a tape alphabet larger than the input alphabet allows the available memory to be increased up to a constant factor. That is, for an input of length $n$, the amount of memory available is linear in $n$, hence the name.

A language is called context-sensitive if a linear bounded automaton recognizes it.