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 nondeterministic 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, weaker 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,[1]:225 due to the linear speedup theorem.

LBA and context-sensitive languages

Linear bounded automata are acceptors for the class of context-sensitive languages.[1]:225-226 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.[2] In 1963, Peter S. Landweber proved that the languages accepted by deterministic LBAs are context-sensitive.[3] In 1964, S.-Y. Kuroda introduced the more general model of (nondeterministic) linear bounded automata, noted that Landweber's proof also works for nondeterministic linear bounded automata, and showed that the languages accepted by them are precisely the context-sensitive languages.[4][5]

LBA problems

In his seminal paper, Kuroda also stated two research challenges, which subsequently became famously known as the "LBA problems": The first LBA problem is whether the class of languages accepted by LBA is equal to the class of languages accepted by deterministic LBA. This problem can be phrased succinctly in the language of computational complexity theory as:

First LBA problem: Is NSPACE(O(n)) = DSPACE(O(n))?

The second LBA problem is whether the class of languages accepted by LBA is closed under complement.

Second LBA problem: Is NSPACE(O(n)) = co-NSPACE(O(n))?

As observed already by Kuroda, a negative answer to the second LBA problem would imply a negative answer to the first problem. But the second LBA problem has an affirmative answer, which is implied by the Immerman–Szelepcsényi theorem proved 20 years after the problem was raised. As of today, the first LBA problem still remains open.


  1. 1 2 3 4 John E. Hopcroft; Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X.
  2. John Myhill (June 1960). Linear Bounded Automata (WADD Technical Note). Wright Patterson AFB, Wright Air Development Division, Ohio.
  3. P.S. Landweber (1963). "Three Theorems on Phrase Structure Grammars of Type 1" (PDF). Information and Control. 6 (2): 131136. doi:10.1016/s0019-9958(63)90169-4.
  4. Sige-Yuki Kuroda (Jun 1964). "Classes of languages and linear-bounded automata" (PDF). Information and Control. 7 (2): 207223. doi:10.1016/s0019-9958(64)90120-2.
  5. Willem J. M. Levelt (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 126–127. ISBN 90-272-3250-4.

External links

This article is issued from Wikipedia - version of the 11/3/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.