Computer science Automata and formal languages Concept
Linear bounded automaton
Summary
A linear bounded automaton is a nondeterministic Turing machine whose head never leaves the part of the tape that holds the input. So it uses only an amount of memory proportional to the length of the input. Linear bounded automata accept exactly the context-sensitive languages. Whether deterministic linear bounded automata accept the same languages as nondeterministic ones is an open question.
Where this leads
1 page builds on this one.
Further reading
About this page
| Tag | KF2JADMJC0 |
|---|---|
| URI | m2://KF2JADMJC0 |
| Kind | concept |
| Writing | W0 stub |
| MSC | 68Q45, 68Q04, 03D10 |
| Specializes | Nondeterministic Turing machine |
| Same as | |
| Changed | 3 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.