Linear bounded automaton

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by MystBot (talk | contribs) at 06:07, 26 July 2011 (r2.7.1) (robot Adding: fr:Automate linéairement borné). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of nondeterministic Turing machine.

Operation

Linear bounded automata satisfy the following three conditions:

  1. Its input alphabet includes two special symbols, serving as left and right endmarkers.
  2. Its transitions may not print other symbols over the endmarkers.
  3. Its transitions may neither move to the left of the left endmarker or to the right of the right endmarker.

As in the definition of Turing machines, 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 to have unbounded length, only a finite contiguous portion of the tape, whose length is a linear function of the length of the initial input, can be accessed by the read/write head. 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. Since the size of the accessible tape is bounded by some linear function of the length of the input, the linear bounded automaton is computationally equivalent to a nondeterministic Turing machine restricted to the portion of the tape containing the input, hence the name linear bounded automaton.[citation needed]

This limitation makes the LBA a somewhat more accurate model of computers that actually exist than a Turing machine, whose definition assumes unlimited tape.

LBA and Context-sensitive Languages

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.

History

In 1960, Myhill introduced an automaton model today known as deterministic linear bounded automaton.[1] Shortly thereafter, Landweber proved that the languages accepted by a deterministic LBA are always context-sensitive.[2] In 1964, Kuroda introduced the more general model of (nondeterministic) linear bounded automata, and showed that the languages accepted by them are precisely the context-sensitive languages.[3]

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 only more than 20 years after the problem was raised. As of 2010, the first LBA problem still remains open.

Notes

  1. ^ Myhill (1960)
  2. ^ Landweber (1963)
  3. ^ Kuroda (1964)

References

  • John Myhill: Linearly Bounded Automata, WADD Technical Note 60-165, Wright-Patterson Air Force Base, Wright Air Development Division, Ohio, June 1960.
  • Peter S. Landweber: Three Theorems on Phrase Structure Grammars of Type 1, Information and Control 6(2): 131-136 (1963)
  • Sige-Yuki Kuroda: Classes of languages and linear-bounded automata, Information and Control, 7(2): 207–223 (1964)

External links

Retrieved from "https://en.wikipedia.org/w/index.php?title=Linear_bounded_automaton&oldid=441480212"