linear-bounded automaton

views updated

linear-bounded automaton (LBA) A Turing machine M such that the number of tape cells visited by M is bounded by some linear function of the length of the input string. Of equivalent power is the smaller class of Turing machines that visit only the cells bearing the input string. The context-sensitive languages are precisely those recognized by such Turing machines.