Linear bounded automaton
Encyclopedia
In computer science
, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of nondeterministic Turing machine.
As in the definition of Turing machine
s, 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.
This limitation makes the LBA a somewhat more accurate model of computer
s that actually exist than a Turing machine, whose definition assumes unlimited tape.
s. 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.
introduced an automaton model today known as deterministic linear bounded automaton. Shortly thereafter, Landweber proved that the languages accepted by a deterministic LBA are always context-sensitive. 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.
theory as:
The second LBA problem is whether the class of languages accepted by LBA is closed under complement.
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 2011, the first LBA problem still remains open.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, 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:- 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 or to the right of the right endmarker.
As in the definition of Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
s, it possesses a tape made up of cells that can contain symbols from a finite alphabet
Alphabet
An alphabet is a standard set of letters—basic written symbols or graphemes—each of which represents a phoneme in a spoken language, either as it exists now or as it was in the past. There are other systems, such as logographies, in which each character represents a word, morpheme, or semantic...
, 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
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
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
Linear function
In mathematics, the term linear function can refer to either of two different but related concepts:* a first-degree polynomial function of one variable;* a map between two vector spaces that preserves vector addition and scalar multiplication....
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.
This limitation makes the LBA a somewhat more accurate model of computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
s 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 languageContext-sensitive language
In theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy...
s. The only restriction placed on grammars
Grammars
Grammars: A Journal of Mathematical Research on Formal and Natural Languages is an academic journal devoted to the mathematical linguistics of formal and natural languages, published by Springer-Verlag.ISSN 1386-7393...
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, MyhillJohn Myhill
John R. Myhill was a mathematician, born in 1923. He received his Ph.D. from Harvard University under Willard Van Orman Quine in 1949. He was professor at SUNY Buffalo from 1966 until his death in 1987...
introduced an automaton model today known as deterministic linear bounded automaton. Shortly thereafter, Landweber proved that the languages accepted by a deterministic LBA are always context-sensitive. In 1964, Kuroda
S.-Y. Kuroda
, aka S.-Y. Kuroda, was Professor Emeritusand Research Professor of Linguistics at the University of California, San Diego.Although a pioneer in the application of Chomskyan generative syntax to...
introduced the more general model of (nondeterministic) linear bounded automata, and showed that the languages accepted by them 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 complexityComputational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
theory as:
- First LBA problem: Is NSPACENSPACEIn computational complexity theory, the complexity class NSPACE is the set of decision problems that can be solved by a non-deterministic Turing machine using space O, and unlimited time. It is the non-deterministic counterpart of DSPACE.Several important complexity classes can be defined in terms...
(O(n)) = DSPACEDSPACEIn computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a...
(O(n))?
The second LBA problem is whether the class of languages accepted by LBA is closed under complement.
- Second LBA problem: Is NSPACENSPACEIn computational complexity theory, the complexity class NSPACE is the set of decision problems that can be solved by a non-deterministic Turing machine using space O, and unlimited time. It is the non-deterministic counterpart of DSPACE.Several important complexity classes can be defined in terms...
(O(n)) = co-NSPACENSPACEIn computational complexity theory, the complexity class NSPACE is the set of decision problems that can be solved by a non-deterministic Turing machine using space O, and unlimited time. It is the non-deterministic counterpart of DSPACE.Several important complexity classes can be defined in terms...
(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 2011, the first LBA problem still remains open.
External links
- Linear Bounded Automata by Forbes D. Lewis
- Linear Bounded Automata slides, part of Context-sensitive Languages by Arthur C. Fleck
- Linear-Bounded Automata , part of Theory of Computation syllabus, by David Matuszek