HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
.


Operation

A linear bounded automaton is a
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
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. 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 A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
, an LBA possesses a tape made up of cells that can contain symbols from a finite
alphabet An alphabet is a standard set of letter (alphabet), letters written to represent particular sounds in a spoken language. Specifically, letters largely correspond to phonemes as the smallest sound segments that can distinguish one word from a ...
, 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 A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
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 In mathematics, the term linear function refers to two distinct but related notions: * In calculus and related areas, a linear function is a function whose graph is a straight line, that is, a polynomial function of degree zero or one. For di ...
of the length of the initial input, can be accessed by the read/write head; hence the name ''linear bounded automaton''. This limitation makes an LBA a somewhat more accurate model of a real-world
computer A computer is a machine that can be Computer programming, programmed to automatically Execution (computing), carry out sequences of arithmetic or logical operations (''computation''). Modern digital electronic computers can perform generic set ...
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''.


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, 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.


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 In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
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. Savitch's theorem provides an initial insight, that NSPACE(O(''n'')) ⊆ DSPACE(O(''n''2)).


References


External links


Linear Bounded Automata
b
Forbes D. Lewis


slides, part o
Context-sensitive Languages
b
Arthur C. Fleck


part of Theory of Computation syllabus, by David Matuszek {{Formal languages and grammars Automata (computation) Models of computation