선형유한 자동 기계

컴퓨터 과학에서 선형유한 자동 기계(linear bounded automaton, LBA)는 계산 능력을 제한한 튜링 기계의 일종이다.

동작편집

선형유한 자동 기계는 다음 세 가지 조건을 만족하는 비결정론적 튜링 기계이다.

  • 입력 문자 중에 왼쪽 끝 표시와 오른쪽 끝 표시의 역할을 하는 2개의 특별 기호가 있다.
  • 끝 표시 위에 다른 기호를 덮어쓸 수 없다.
  • 왼쪽 끝 표시보다 왼쪽으로 가거나 오른쪽 끝 표시보다 오른쪽으로 갈 수 없다.[1]:225

즉, 일반적인 튜링 기계처럼 무한한 길이의 테이프 위에서 계산하지 못하고, 테이프에서 입력 내용과 양쪽 끝 표시를 포함하는 부분 안에서만 계산할 수 있다.

이보다 덜 제한적인 또다른 정의가 있다.

  • 튜링 기계와 마찬가지로, 선형유한 자동 기계는 다음 요소로 구성된다.
    • 칸들로 이루어진 테이프. 테이프의 각 칸에는 유한한 알파벳에서 나온 기호 하나를 기록할 수 있다.
    • 테이프 헤드. 테이프 헤드는 좌우로 움직이면서 칸에 있는 기호를 읽거나 다른 기호를 덮어쓸 수 있다.
    • 유한한 수의 상태. 현재 상태와 헤드가 읽은 기호에 따라 기계의 다음 동작이 정해진다.
  • 튜링 기계와 달리, 선형유한 자동 기계가 사용할 수 있는 테이프의 길이는 입력의 길이에 대한 일차함수로 제한된다. ‘선형유한’이라는 이름은 여기서 나온 것이다.[1]:225

이러한 제한 때문에 선형유한 자동 기계는 무한한 테이프 길이를 가정하는 튜링 기계에 비해 현실의 컴퓨터와 더 비슷하다.

선형 가속 정리 때문에 위의 두 가지 정의는 사실 똑같은 계산 능력을 지닌다.[1]:225

선형유한 자동 기계와 문맥 의존 언어편집

선형유한 자동 기계는 문맥 의존 언어에 대응하는 기계이다.[1]:225-226 문맥 의존 언어를 만드는 형식 문법에 대한 제약은 하나뿐으로, 어떤 생성 규칙도 문자열을 더 짧은 문자열로 바꿔선 안 된다는 것이다. 따라서 문맥 의존 언어에 속한 문자열의 도출 과정에서는 그 문자열보다 더 긴 중간 단계가 나타나지 않는다. 이러한 문법은 선형유한 자동 기계와 일대일 대응하므로, 선형유한 자동 기계가 어느 문자열을 인식하는 데는 이 문자열을 입력할 테이프 공간보다 더 많은 공간이 필요하지 않다.

역사편집

1960년에 존 마이힐은 오늘날 결정론적 선형유한 자동 기계라 불리는 개념을 도입했다.[2] 1963년에 피터 랜드웨버는 결정론적 선형유한 자동 기계가 수용하는 언어들이 문맥 의존 언어임을 증명했다.[3] 1964년에 구로다 시게유키는 보다 일반적인 개념인 (비결정론적) 선형유한 자동 기계의 개념을 도입하고, 랜드웨버의 증명이 비결정론적 LBA에도 적용될 수 있다고 지적했으며, 비결정론적 LBA가 수용하는 언어들의 집합이 정확히 문맥 의존 언어들의 집합과 같음을 증명했다.[4][5]

LBA 문제편집

구로다가 1964년 논문에서 제기한 두 가지 문제는 이후 “LBA 문제”라는 이름으로 유명해졌다. 첫번째 LBA 문제는 일반적인 LBA와 결정론적 LBA가 수용하는 언어들의 집합이 같냐는 것이었다. 계산 복잡도 이론의 용어로는 다음과 같이 간단히 나타낼 수 있다.

첫번째 LBA 문제: NSPACE(O(n)) = DSPACE(O(n))인가?

두번째 LBA 문제는 LBA가 수용하는 언어들의 집합이 여집합 연산에 대해 닫혀 있냐는 것이었다.

두번째 LBA 문제: NSPACE(O(n)) = co-NSPACE(O(n))인가?

구로다가 지적했듯이, 두번째 LBA 문제의 답이 ‘거짓’이라면 첫번째 문제의 답도 ‘거짓’이다. 그러나 20년 뒤에 증명된 이머만-셀레프체니 정리에 따라 두번째 문제의 답은 ‘참’으로 드러났다.[6][7] 현재까지도 첫번째 LBA 문제는 해결되지 않았다. 사비치의 정리에 따라 NSPACE(O(n)) ⊆ DSPACE(O(n2))이라는 사실은 알려져 있다.[8]

각주편집

  1. 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. 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 961049 
  7. Szelepcsényi, Róbert (1988), “The method of forcing for nondeterministic automata”, 《Acta Informatica》 26 (3): 279–284 
  8. Arora, Sanjeev; Barak, Boaz (2009). 《Complexity Theory: A Modern Approach》. Cambridge University Press. ISBN 978-0-521-42426-4. 

외부편집