위키백과

선형유한 자동 기계

컴퓨터 과학에서 선형유한 자동 기계(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. 

외부 편집

원본 주소 "https://ko.wikipedia.org/w/index.php?title=선형유한_자동_기계&oldid=33563689"