Linear bounded automaton

A linear time Turing machine (also LBA = Linear Bounded Automaton ) is a Turing machine that does not leave the area of ​​the tape on which the input is. Thus, during the entire calculation, only the part of the tape is used at the beginning was the input word.

LBA is greater by a constant factor band simulate by containing the band of the input alphabet tuple alphabet. Similarly, a definition would be conceivable in which a greater by a constant factor equal band provided. That is, there is a constant number, so that the Turing machine uses at most the first fields of the strip, the length of the input word is. The usable length of tape, then, is linear in the length of the input. This explains the "Linear" on behalf of the LBA.

The language accepted by non-deterministic LBAs languages ​​are exactly the context-sensitive languages ​​(see Chomsky hierarchy ).

It is an open problem whether deterministic LBAs accept the same language class as the non-deterministic.

• Automata Theory