Linear bounded automaton
A linear bounded automaton (LBA) is an abstract machine that would be identical to a Turing machine, except that during a computation with given input its tape-head is not allowed to move outside a bounded region of its infinite tape, the number of accessible tape-cells being a linear function of the input-size. The tape itself has infinite length in order to accomodate inputs of arbitrary length. (An equivalent alternative version of this model supplies the LBA with a different finite-length tape for each input of different size, the length of the tape being a linear function of the input-size. In this alternative version, there is a supply of infinitely many finite tapes, there being one tape for each input-size.)
Like the Turing machine, an LBA is a finite state machine equipped with a tape. Unlike a Turing machine system, an LBA system (the finite state machine plus its tape) has only finitely many system states for each input; that is, for each input, an LBA system behaves as a finite automaton. A pertinent difference between an LBA and a FSA is that the number of states of an FSA is fixed for that FSA, while the number of states of an LBA varies as a linear function of the amount of input given to that LBA.
It is possible to show, using the Pumping lemma, that there are languages which are recognized by some LBA that cannot be recognized by any push-down automaton. Linear-bounded automata recognize the class of context-sensitive languages.
History
Myhill[1960] introduced LBAs, motivated by the research of Rabin and Scott[1959] on finite automata.
See also
- Category:Linear bounded automata (a list of languages on this wiki which have equivalent power to an LBA)