Talk:Linear bounded automaton

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:

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]

Is the requirement that the string maps to shorter or equal or longer or equal string?

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]

Nondeterministic?

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]

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

404 page for broken link

DragonGod2718 (talk) 13:39, 20 August 2024 (UTC)[reply]

Formal Definition of LBA

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]

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.