This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computer science This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science ??? This article has not yet received a rating on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Hello fellow Wikipedians,

I have just modified 2 external links on Linear bounded automaton. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20070205070159/http://www.cs.uky.edu/~lewis/texts/theory/automata/lb-auto.pdf to http://www.cs.uky.edu/~lewis/texts/theory/automata/lb-auto.pdf
• Added archive https://web.archive.org/web/20070109012311/http://www.cs.uky.edu/~lewis/ to http://www.cs.uky.edu/~lewis/

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 18:45, 23 December 2017 (UTC)Reply

I'm confused by this: "The only restriction placed on grammars for such languages is that no production maps a string to a shorter string." I don't understand how does the conclusion "Thus no derivation of a string in a context-sensitive language can contain a sentential form longer than the string itself." follows. What the first says is that S -> SS | x is a valid LBA grammar, but this clearly maps S to SS, then to SSS, then to SSSS and so on. 141.226.245.164 (talk) 16:13, 15 January 2018 (UTC)Reply

Yes, your example grammar is a valid context-sensitive grammar. - In your example, none of the sentential forms is shorter than any of its predecessors in your derivation chain. So where is your problem in this example? - Jochen Burghardt (talk) 18:13, 15 January 2018 (UTC)Reply

The Operation section says, "A linear bounded automaton is a nondeterministic Turing machine". But the History section says, "In 1960, John Myhill introduced an automaton model today known as deterministic linear bounded automaton." This suggests there are both deterministic and nondeterministic versions of the machine. This should be clarified. Mdbirken (talk) 19:00, 9 July 2022 (UTC)Reply

• Linear-Bounded Automata, part of Theory of Computation syllabus, by David Matuszek

This link doesn't work (it gives me a 404 page):

DragonGod2718 (talk) 13:39, 20 August 2024 (UTC)Reply

I was hoping to see a formal tuple definition of an LBA (analogous to the one provided for a Turing machine). It is mentioned that it's a restricted variant of a Turing machine, but it's not at all clear to me whether this restriction changes the formal definition of an LBA or not. DragonGod2718 (talk) 13:40, 20 August 2024 (UTC)Reply

Regarding recent reversals: The intent was to bridge the gap between the theoretical definition of an LBA and its physical realization in software (e.g., in minimalist Lisp evaluators). While Tail Call Optimization (TCO) alone does not define an LBA, it is a necessary mechanism to ensure the stack portion of the memory remains strictly bounded (O(1) space). When combined with destructive memory updates (reusable heap cells), the resulting execution engine satisfies the linear space constraints of an LBA. I propose a refined version that focuses on "Physical Realization" rather than total formal equivalence. Agreppin (talk) 04:56, 9 June 2026 (UTC)Reply

I'm discussing your above text and your recent addition

"While the Linear Bounded Automaton is a theoretical construct, its memory constraints are a practical reality in bare-metal and embedded computing. In these environments, strict tail-call optimization is often employed as a primary mechanism to ensure that the stack space remains strictly bounded (O(1) space) during recursion. When combined with in-place memory reuse (such as destructive list updates), these engines can process data without exceeding the fixed, linear memory boundaries of the hardware, effectively functioning as a physical implementation of an LBA."

• An LBA has at least as much memory available as its input is long. In contrast, bare-metal and embedded computing can provide only a fixed amount of memory (corresponding to a finite automaton).
• In the article lead, there is an alternative, less restrictive definition that allows an LBA to have up to, say, ten times as much memory as its input is long.
• You are right in that tail-call optimization may reduce the memory need of a program such that it fits into given memory while the unoptimized version did not. However, there are many optimizations that may have a similar effect. This article is not the right place to introduce them all. And neither is any of the other articles about formal language classes.

Best regards, Jochen Burghardt (talk) 15:35, 9 June 2026 (UTC)Reply