선형유한 자동 기계: 두 판 사이의 차이

1960년에 [[존 마이힐]]은 오늘날 결정론적 선형유한 자동 기계라 불리는 개념을 도입했다.<ref>{{cite report | author=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> 1963년에 [[피터 랜드위버랜드웨버]]는 결정론적 선형유한 자동 기계가 수용하는 언어들이 문맥 의존 언어임을 증명했다.<ref>{{cite journal | author=P.S. Landweber | title=Three Theorems on Phrase Structure Grammars of Type 1 | journal=Information and Contro] | volume=6 | number=2 | pages=131–136 | year=1963 | doi=10.1016/s0019-9958(63)90169-4| doi-access=free }}</ref> 1964년에 [[구로다 시게유키]]는 보다 일반적인 개념인 (비결정론적) 선형유한 자동 기계의 개념을 도입하고, 랜드웨버의 증명이 비결정론적 기계에도LBA에도 적용될 수 있다고 지적했으며, 비결정론적 LBA가 수용하는 언어들의 집합이 정확히 문맥 의존 언어들의 집합과 같음을 증명했다.<ref>{{cite journal | author=Sige-Yuki Kuroda | authorlink=구로다 시게유키 |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| 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>