선형유계오토마톤

Linear bounded automaton

컴퓨터 과학에서, 선형 유계 오토마톤(복수 선형 유계 오토마타, 약어 LBA)은 튜링 기계의 제한된 형태이다.

작동

선형 유계 오토마톤은 다음 세 가지 조건을 만족시키는 비결정론적 튜링 기계이다.

  • 입력 알파벳에는 두 개의 특수 기호가 포함되어 있으며, 왼쪽 및 오른쪽 엔드마커 역할을 합니다.
  • 변환 시 엔드마커 위에 다른 기호가 인쇄되지 않을 수 있습니다.
  • 전환은 왼쪽 엔드마커의 왼쪽이나 오른쪽 엔드마커의 오른쪽으로 [1]: 225 이동할 수 없습니다.

즉, 계산해야 할 테이프가 무한대일 가능성이 있는 것이 아니라 입력과 엔드마커를 유지하는 2개의 테이프 정사각형을 포함하는 테이프의 부분으로 계산이 제한됩니다.

제한적인 대체 정의는 다음과 같습니다.

  • 튜링 기계와 같이, LBA는 유한한 알파벳의 기호를 포함할 수 있는 셀, 테이프 상의 한 셀에서 한 번에 읽거나 쓸 수 있고 이동할 수 있는 헤드, 그리고 유한한 수의 상태를 가지고 있다.
  • LBA는 처음에 테이프가 무제한 길이를 갖는 것으로 간주되는 반면, 읽기/쓰기 헤드에 의해 길이가 선형 함수인 테이프의 유한한 연속 부분만 접근할 수 있다는 점에서 튜링 [1]: 225 기계와 다르다.

이러한 제한은 LBA를 튜링 머신보다 실제 컴퓨터의 어느 정도 더 정확한 모델로 만듭니다. 튜링 머신의 정의는 무제한 테이프를 가정합니다.

강한 정의와 약한 정의는 선형 속도 향상 정리 때문에 각각의 오토마톤 [1]: 225 클래스의 동일한 계산 능력을 이끈다.

LBA 및 컨텍스트 의존 언어

선형 유계 오토마타는 상황에 맞는 [1]: 225–226 언어 클래스의 수용자입니다.이러한 언어의 문법에 대한 유일한 제한은 문자열을 짧은 문자열에 매핑하는 프로덕션 기능이 없다는 것입니다.따라서 문맥 의존형 언어의 문자열 파생은 문자열 자체보다 긴 센텐셜 형식을 포함할 수 없습니다.선형 경계 오토마타와 이러한 문법은 일대일 대응이 있기 때문에, 오토마톤에 의해서 인식되기 위해서, 원래의 문자열이 차지하는 테이프 이상의 테이프는 불필요하다.

역사

1960년, John Myhill은 결정론적 선형 유계 오토마톤으로 [2]알려진 오토마톤 모델을 발표했습니다.1963년, 피터 랜드웨버는 결정론적 LBA에 의해 받아들여진 언어가 문맥에 [3]민감하다는 것을 증명했다.1964년 S.-Y. 쿠로다는 (비결정론적) 선형 경계 오토마타의 보다 일반적인 모델을 도입했고, 랜드웨버의 증명은 비결정론적 선형 경계 오토마타에도 적용된다는 것을 지적했으며, 그들이 받아들이는 언어는 정확하게 문맥에 민감한 [4][5]언어라는 것을 보여주었다.

LBA 문제

Kuroda는 또한 그의 학술 논문에서 다음과 같은 두 가지 연구 과제를 언급했는데, 이는 후에 "LBA 문제"로 유명해졌다.첫 번째 LBA 문제는 LBA에 의해 받아들여지는 언어 클래스가 결정론적인 LBA에 의해 받아들여지는 언어 클래스와 동일한지 여부입니다.이 문제는 계산 복잡도 이론의 언어로 다음과 같이 간결하게 표현될 수 있습니다.

번째 LBA 문제:NSPACE(O(n) = DSPACE(O(n))입니까?

두 번째 LBA 문제는 LBA가 받아들이는 언어 클래스가 보완 하에 폐쇄되는지 여부입니다.

번째 LBA 문제:NSPACE(O(n) = co-NSPACE(O(n))입니까?

쿠로다가 이미 관찰한 바와 같이, 제2의 LBA 문제에 대한 부정적 답변은 제1의 문제에 대한 부정적 답변을 의미한다.그러나 두 번째 LBA 문제는 긍정적인 답변을 가지고 있으며, 이는 문제가 [6][7]제기된 지 20년 후에 증명된 이머만-제렙세니 정리에 의해 암시된다.현재 첫 번째 LBA 문제는 아직 해결되지 않은 상태입니다.Savitch의 정리는 NSPACE(O(n) d DSPACE(O(n2))[8]라는 초기 통찰력을 제공한다.

레퍼런스

  1. ^ a b c d John E. Hopcroft; Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 978-0-201-02988-8.
  2. ^ John Myhill (June 1960). Linear Bounded Automata (WADD Technical Note). Wright Patterson AFB, Wright Air Development Division, Ohio.
  3. ^ P.S. Landweber (1963). "Three Theorems on Phrase Structure Grammars of Type 1". Information and Control. 6 (2): 131–136. doi:10.1016/s0019-9958(63)90169-4.
  4. ^ Sige-Yuki Kuroda (Jun 1964). "Classes of languages and linear-bounded automata". Information and Control. 7 (2): 207–223. doi:10.1016/s0019-9958(64)90120-2.
  5. ^ Willem J. M. Levelt (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 126–127. ISBN 978-90-272-3250-2.
  6. ^ Immerman, Neil (1988), "Nondeterministic space is closed under complementation" (PDF), SIAM Journal on Computing, 17 (5): 935–938, doi:10.1137/0217058, MR 0961049
  7. ^ Szelepcsényi, Róbert (1988), "The method of forcing for nondeterministic automata", Acta Informatica, 26 (3): 279–284, doi:10.1007/BF00299636, S2CID 10838178
  8. ^ Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.

외부 링크