Linear bounded automaton: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 03:06, 29 November 2024

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

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(n²)).^[8]

References

^ ^a ^b ^c ^d Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 0-201-02988-X. (accessible to patrons with print disabilities)
^ 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
^ Szelepcsényi, Róbert (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

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

[Hopcroft.Ullman.1979-1] Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 0-201-02988-X. (accessible to patrons with print disabilities)

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

[6] Immerman, Neil (1988), "Nondeterministic space is closed under complementation" (PDF), SIAM Journal on Computing, 17 (5): 935–938, doi:10.1137/0217058, MR 0961049

[7] Szelepcsényi, Róbert (1988), "The method of forcing for nondeterministic automata", Acta Informatica, 26 (3): 279–284, doi:10.1007/BF00299636, S2CID 10838178

[8] Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Line 1: / Line 1: @@
+{{Short description|Type of Turing machine}}
 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:
+A linear bounded automaton is a [[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.<ref name="Hopcroft.Ullman.1979">{{cite book| author=John E. Hopcroft, Jeffrey D. Ullman| title=Introduction to Automata Theory, Languages, and Computation| year=1979| publisher=Addison-Wesley| isbn=0-201-02988-X}}</ref>{{rp|225}}
+* Its transitions may neither move to the left of the left endmarker nor to the right of the right endmarker.<ref name="Hopcroft.Ullman.1979">{{Hopcroft and Ullman 1979}}</ref>{{rp|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, '''weaker definition''' is as follows:
+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 set|finite]] [[alphabet (computer science)|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''.<ref name="Hopcroft.Ullman.1979"/>{{rp|225}}
@@ Line 16: / Line 17: @@
 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,<ref name="Hopcroft.Ullman.1979"/>{{rp|225}} due to the ''[[linear speedup theorem]]''.
+The strong and the weaker definition lead to the same computational abilities of the respective automaton classes,<ref name="Hopcroft.Ullman.1979"/>{{rp|225}} by the same argument used to prove the ''[[linear speedup theorem]]''.
 ==LBA and context-sensitive languages==
-Linear bounded automata are [[Finite_state_machine#Acceptors_and_recognizers|acceptors]] for the class of [[context-sensitive language]]s.<ref name="Hopcroft.Ullman.1979"/>{{rp|225-226}}  The only restriction placed on [[Formal_grammar|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.
+Linear bounded automata are [[acceptor (finite-state machine)|acceptor]]s for the class of [[context-sensitive language]]s.<ref name="Hopcroft.Ullman.1979"/>{{rp|225-226}}  The only restriction placed on [[Formal_grammar|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.<ref>Myhill (1960)</ref> In 1963, Peter S. Landweber proved that the languages accepted by deterministic LBAs are context-sensitive.<ref>Landweber (1963)</ref> 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.<ref>Kuroda (1964)</ref><ref>{{cite book|author=Willem J. M. Levelt|title=An Introduction to the Theory of Formal Languages and Automata|url=http://books.google.com/books?id=tFvtwGYNe7kC&pg=PA126|year=2008|publisher=John Benjamins Publishing|isbn=90-272-3250-4|pages=126–127}}</ref>
+In 1960, [[John Myhill]] introduced an automaton model today known as deterministic linear bounded automaton.<ref>{{cite report | author=John Myhill | authorlink=John Myhill | title=Linear Bounded Automata | institution=Wright Patterson AFB, Wright Air Development Division, Ohio | type=WADD Technical Note | number=60–165  | date=June 1960 }}</ref> In 1963, [[Peter Landweber]] proved that the languages accepted by deterministic LBAs are context-sensitive.<ref>{{cite journal | author=P.S. Landweber | title=Three Theorems on Phrase Structure Grammars of Type 1 | journal=[[Information and Control]] | volume=6 | number=2 | pages=131–136 | year=1963 | doi=10.1016/s0019-9958(63)90169-4| doi-access=free }}</ref> 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.<ref>{{cite journal | author=Sige-Yuki Kuroda | authorlink=Sige-Yuki Kuroda |title=Classes of languages and linear-bounded automata | journal=Information and Control | volume=7 | number=2 | pages=207–223 | date=Jun 1964 | doi=10.1016/s0019-9958(64)90120-2| doi-access=free }}</ref><ref>{{cite book|author=Willem J. M. Levelt| authorlink=Willem Levelt| title=An Introduction to the Theory of Formal Languages and Automata|url=https://books.google.com/books?id=tFvtwGYNe7kC&pg=PA126|year=2008|publisher=John Benjamins Publishing|isbn=978-90-272-3250-2|pages=126–127}}</ref>
 ==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:
+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))?
+:'''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))?
+:'''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 2014, the first LBA problem still remains open.
+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.<ref>{{citation | last = Immerman | first = Neil | authorlink = Neil Immerman | doi = 10.1137/0217058 | issue = 5 | journal = [[SIAM Journal on Computing]] | mr = 961049 | pages = 935–938 | title = Nondeterministic space is closed under complementation | url = http://www.cs.umass.edu/~immerman/pub/space.pdf | volume = 17 | year = 1988}}</ref><ref>{{citation | last = Szelepcsényi | first = Róbert | author-link = Róbert Szelepcsényi | journal = [[Acta Informatica]] | pages = 279–284 | title = The method of forcing for nondeterministic automata | volume = 26 | issue = 3 | year = 1988| doi = 10.1007/BF00299636 | s2cid = 10838178 }}</ref> As of today, the first LBA problem still remains open. [[Savitch's theorem]] provides an initial insight, that '''NSPACE'''(O(''n'')) ⊆ '''DSPACE'''(O(''n''<sup>2</sup>)).<ref>{{cite book |last1= Arora |first1= Sanjeev |authorlink = Sanjeev Arora|last2= Barak |first2= Boaz |author2link = Boaz Barak|url= http://www.cs.princeton.edu/theory/complexity/ |title= Complexity Theory: A Modern Approach |publisher= Cambridge University Press |date= 2009 |isbn= 978-0-521-42426-4 }}</ref>
-==Notes==
+==References==
 <references/>
-==References==
-{{refbegin}}
-* {{cite report | author=John Myhill | authorlink=John Myhill | title=Linear Bounded Automata | institution=Wright Patterson AFB, Wright Air Development Division, Ohio | type=WADD Technical Note | number=60-165  | date=June 1960 }}
-* {{cite journal | author=P.S. Landweber | title=Three Theorems on Phrase Structure Grammars of Type 1 | journal=[[Information and Control]] | volume=6 | number=2 | pages=131&mdash;136 | url=http://www.sciencedirect.com/science/article/pii/S0019995863901694/pdf?md5=15d5b2836e2e59a70ed02fb4074b63f9&pid=1-s2.0-S0019995863901694-main.pdf | year=1963 }}
-* {{cite journal | author=Sige-Yuki Kuroda | authorlink=Sige-Yuki Kuroda |title=Classes of languages and linear-bounded automata | journal=Information and Control | volume=7 | number=2 | pages=207&mdash;223 | url=http://www.sciencedirect.com/science/article/pii/S0019995864901202/pdf?md5=0a10da0e20ccd77c5d61461764f42e5f&pid=1-s2.0-S0019995864901202-main.pdf | date=Jun 1964 }}
-{{refend}}
 == External links ==
-* [http://www.cs.uky.edu/~lewis/texts/theory/automata/lb-auto.pdf Linear Bounded Automata] by [http://www.cs.uky.edu/~lewis/ Forbes D. Lewis]
+* [https://web.archive.org/web/20070205070159/http://www.cs.uky.edu/~lewis/texts/theory/automata/lb-auto.pdf Linear Bounded Automata] by [https://web.archive.org/web/20070109012311/http://www.cs.uky.edu/~lewis/ Forbes D. Lewis]
 * [http://www.cs.uiowa.edu/~fleck/PartIIIxpar/sld006.htm Linear Bounded Automata] slides, part of [http://www.cs.uiowa.edu/~fleck/PartIIIxpar/ Context-sensitive Languages] by [http://www.cs.uiowa.edu/~fleck Arthur C. Fleck]
 * [http://www.seas.upenn.edu/~cit596/notes/dave/chomsky2.html Linear-Bounded Automata], part of Theory of Computation syllabus, by David Matuszek
@@ Line 48: / Line 42: @@
 {{Formal languages and grammars}}
-[[Category:Automata theory]]
+[[Category:Automata (computation)]]
 [[Category:Models of computation]]