A linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of a Turing machine. It possesses a tape made up of cells that can contain symbols from a finitealphabet, 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. An artistic representation of a Turing Machine . ... In mathematics, a set is called finite if and only if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... An alphabet is a complete standardized set of letters — basic written symbols — each of which roughly represents a phoneme of a spoken language, either as it exists now or as it may have been in the past. ... A linear function is a mathematical function term of the form: f(x) = m x + c where c is a constant. ... A drawing of the everyday computer. ...
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. A context-sensitive language is a formal language that can be defined by a context-sensitive grammar. ... This article is about grammar from a linguistic perspective. ...
Informally, a pushdownautomaton is a finiteautomaton that can make use of a stack.
The (underlying) finiteautomaton is specifically a nondeterministic finite state machine, giving what is technically known as a "nondeterministic pushdownautomaton" (NPDA).
A linearboundedautomaton is a device which is more powerful than a pushdownautomaton but less so than a Turing machine.
Linearbounded automata are accepters for the class of context-sensitive languages.
Informally, a pushdownautomaton is a finiteautomatonfinite state machine (FSM) or finiteautomaton is a model of behaviour composed of states, transitions and actions.
The finiteautomaton is usually a nondeterministic finite state machine nondeterministic finite state machine or nondeterministic finiteautomaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states.
Feeds |
Contact