A linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of a non-deterministic Turing machine. It possesses a tape made up of cells that can contain symbols from a finite alphabet, a head that can read from or write to one cell on the tape at a time and can be moved, and a finite number of states. It differs from a Turing machine in that while the tape is initially considered infinite, only a finite contiguous portion whose length is a linear function of the length of the initial input can be accessed by the read/write head. This limitation makes an LBA a more accurate model of computers that actually exist than a Turing machine in some respects.

Linear bounded automata are accepters for the class of context-sensitive languages. The only restriction placed on grammars for such languages is that no production maps a string to a shorter string. Thus no derivation of a string in a context-sensitive language can contain a sentential form longer than the string itself. Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string to be recognized by the automaton.

Computational models

Lineárně ohraničený Turingův stroj | Linear beschränkte Turingmaschine | Automa lineare limitato | 線形拘束オートマトン