Editing Context-sensitive grammar (section)

=== Equivalence to linear bounded automaton ===
A formal language can be described by a context-sensitive grammar if and only if it is accepted by some [[linear bounded automaton]] (LBA).<ref>(Hopcroft, Ullman, 1979); Theorem 9.5, 9.6, p.&nbsp;225–226</ref> In some textbooks this result is attributed solely to Landweber and [[S.-Y. Kuroda|Kuroda]].<ref name="DavisSigal1994b"/> Others call it the [[John Myhill|Myhill]]–Landweber–Kuroda theorem.<ref name="flac">{{Cite web |first=Klaus |last=Sutner |url=https://www.cs.cmu.edu/~flac/pdf/ContSens.pdf |title=Context Sensitive Grammars |publisher=[[Carnegie Mellon University]] |date=Spring 2016 |access-date=2019-08-29 |archive-date=2017-02-03 |archive-url=https://web.archive.org/web/20170203081505/http://www.cs.cmu.edu/~flac/pdf/ContSens.pdf |url-status=dead }}</ref> (Myhill introduced the concept of deterministic LBA in 1960. Peter S. Landweber published in 1963 that the language accepted by a deterministic LBA is 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&ndash;136 | year=1963 |doi=10.1016/s0019-9958(63)90169-4 | doi-access=free }}</ref> Kuroda introduced the notion of non-deterministic LBA and the equivalence between LBA and CSGs in 1964.<ref>{{cite book|first=Alexander|last=Meduna|author-link=Alexander Meduna|title=Automata and Languages: Theory and Applications|url=https://books.google.com/books?id=s7gEErax71cC&pg=PA755|year=2000|publisher=Springer Science & Business Media|isbn=978-1-85233-074-3|page=755}}</ref><ref>{{cite book|first=Willem J. M.|last=Levelt|author-link=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>)

{{As of|2010}}{{update inline|date=May 2023}} it is still an open question whether every context-sensitive language can be accepted by a ''deterministic'' LBA.<ref>{{cite book|last=Martin|first=John C.|title=Introduction to Languages and the Theory of Computation|year=2010|publisher=McGraw-Hill|location=New York, NY|isbn=9780073191461|edition=4th|page=283}}</ref>