Jump to content

Linear bounded automaton

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 167.102.76.133 (talk) at 19:49, 4 November 2019 (gfgbrthnvnhthyfh). 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 Turing machine.

Operation

A linear bounded automaton is a nondeterministic Turing machine that satisfies the following three conditions:

  • Its input alphabet includes two special symbols, serving as left and right endmarkers.
  • Its transitions may not print other symbols over the endmarkers.
  • Its transitions may neither move to the left of the left endmarker nor to the right of the right endmarker.[1]: 225 

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:

  • Like a Turing machine, an LBA 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.
  • An LBA 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; hence the name linear bounded automaton.[1]: 225 

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.

History

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]

References

  1. ^ a b c d John E. Hopcroft; Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 978-0-201-02988-8.
  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". Information and Control. 6 (2): 131–136. doi:10.1016/s0019-9958(63)90169-4.
  4. ^ Sige-Yuki Kuroda (Jun 1964). "Classes of languages and linear-bounded automata". Information and Control. 7 (2): 207–223. 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 978-90-272-3250-2.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Linear_bounded_automaton&oldid=924590739"