Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Linear bounded automaton
In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of Turing machine.
A linear bounded automaton is a Turing machine that satisfies the following three conditions:
In other words: instead of having potentially infinite tape on which to compute, computation is restricted to the portion of the tape containing the input plus the two tape squares holding the endmarkers.
An alternative, less restrictive definition is as follows:
This limitation makes an LBA a somewhat more accurate model of a real-world computer than a Turing machine, whose definition assumes unlimited tape.
The strong and the weaker definition lead to the same computational abilities of the respective automaton classes, by the same argument used to prove the linear speedup theorem.
Linear bounded automata are acceptors 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.
In 1960, John Myhill introduced an automaton model today known as deterministic linear bounded automaton. In 1963, Peter Landweber proved that the languages accepted by deterministic LBAs are context-sensitive. In 1964, S.-Y. Kuroda introduced the more general model of (nondeterministic) linear bounded automata, and adapted Landweber's proof to show that the languages accepted by nondeterministic linear bounded automata are precisely the context-sensitive languages.
Hub AI
Linear bounded automaton AI simulator
(@Linear bounded automaton_simulator)
Linear bounded automaton
In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of Turing machine.
A linear bounded automaton is a Turing machine that satisfies the following three conditions:
In other words: instead of having potentially infinite tape on which to compute, computation is restricted to the portion of the tape containing the input plus the two tape squares holding the endmarkers.
An alternative, less restrictive definition is as follows:
This limitation makes an LBA a somewhat more accurate model of a real-world computer than a Turing machine, whose definition assumes unlimited tape.
The strong and the weaker definition lead to the same computational abilities of the respective automaton classes, by the same argument used to prove the linear speedup theorem.
Linear bounded automata are acceptors 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.
In 1960, John Myhill introduced an automaton model today known as deterministic linear bounded automaton. In 1963, Peter Landweber proved that the languages accepted by deterministic LBAs are context-sensitive. In 1964, S.-Y. Kuroda introduced the more general model of (nondeterministic) linear bounded automata, and adapted Landweber's proof to show that the languages accepted by nondeterministic linear bounded automata are precisely the context-sensitive languages.