Linear bounded automaton
From Wikipedia, the free encyclopedia
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.
| Automata theory: formal languages and formal grammars | |||
|---|---|---|---|
| Chomsky hierarchy |
Grammars | Languages | Minimal automaton |
| Type-0 | Unrestricted | Recursively enumerable | Turing machine |
| n/a | (no common name) | Recursive | Decider |
| Type-1 | Context-sensitive | Context-sensitive | Linear-bounded |
| Type-2 | Context-free | Context-free | Pushdown |
| Type-3 | Regular | Regular | Finite |
| Each category of languages or grammars is a proper subset of the category directly above it. | |||
