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 finitealphabet, 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 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.[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 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, and adapted Landweber's proof to show that the languages accepted by nondeterministic linear bounded automata 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.[6][7] As of today, the first LBA problem still remains open. Savitch's theorem provides an initial insight, that NSPACE(O(n)) ⊆ DSPACE(O(n2)).[8]
^John Myhill (June 1960). Linear Bounded Automata (WADD Technical Note). Wright Patterson AFB, Wright Air Development Division, Ohio.
^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.
^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.
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
January 20, 2023
linear, bounded, automaton, computer, science, linear, bounded, automaton, plural, linear, bounded, automata, abbreviated, restricted, form, turing, machine, contents, operation, context, sensitive, languages, history, problems, references, external, linksoper. In computer science a linear bounded automaton plural linear bounded automata abbreviated LBA is a restricted form of Turing machine Contents 1 Operation 2 LBA and context sensitive languages 3 History 4 LBA problems 5 References 6 External linksOperation EditA 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 by the same argument used to prove the linear speedup theorem LBA and context sensitive languages EditLinear 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 EditIn 1960 John Myhill introduced an automaton model today known as deterministic linear bounded automaton 2 In 1963 Peter 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 and adapted Landweber s proof to show that the languages accepted by nondeterministic linear bounded automata are precisely the context sensitive languages 4 5 LBA problems EditIn 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 Szelepcsenyi theorem proved 20 years after the problem was raised 6 7 As of today the first LBA problem still remains open Savitch s theorem provides an initial insight that NSPACE O n DSPACE O n2 8 References Edit 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 John Myhill June 1960 Linear Bounded Automata WADD Technical Note Wright Patterson AFB Wright Air Development Division Ohio 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 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 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 Immerman Neil 1988 Nondeterministic space is closed under complementation PDF SIAM Journal on Computing 17 5 935 938 doi 10 1137 0217058 MR 0961049 Szelepcsenyi Robert 1988 The method of forcing for nondeterministic automata Acta Informatica 26 3 279 284 doi 10 1007 BF00299636 S2CID 10838178 Arora Sanjeev Barak Boaz 2009 Complexity Theory A Modern Approach Cambridge University Press ISBN 978 0 521 42426 4 External links EditLinear 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 Retrieved from https en wikipedia org w index php title Linear bounded automaton amp oldid 1130857022, wikipedia, wiki, book, books, library,
