튜링 머신(Turing Machine)이란?
튜링 머신은 0형 문법(type 0 grammar)으로 생성되는 언어의 문자열을 받아들이기 위해 사용되는 장치입니다. 튜링 머신(TM)은 입력이 주어지는 셀(cell)로 구분된 무한한 길이의 테이프로 이루어진 수학적 모델로, 입력 테이프를 읽는 헤드(head)를 가집니다. 상태 레지스터(state register)는 튜링 머신의 현재 상태를 저장합니다. 입력 기호를 하나 읽으면 그 기호를 다른 기호로 교체하고, 내부 상태를 변경한 뒤, 오른쪽 또는 왼쪽 셀로 이동합니다. TM이 최종 상태(final state)에 도달하면 입력 문자열은 받아들여지고(accept), 그렇지 않으면 거부됩니다(reject).
튜링 머신은 다음과 같은 7-튜플(Q, X, Σ, δ, q₀, B, F)로 형식적으로 정의할 수 있습니다.
- Q: 유한한 상태의 집합
- X: 테이프 알파벳(tape alphabet)
- Σ: 입력 알파벳(input alphabet)
- δ: 전이 함수(transition function), δ : Q × X → Q × X × {Left_shift, Right_shift}
- q₀: 초기 상태(initial state)
- B: 공백(blank) 기호
- F: 최종 상태(final states)의 집합
목표 언어
우리의 목표는 다음 언어를 받아들이는 튜링 머신을 구성하는 것입니다.
L = { aⁿbᵐa⁽ⁿ⁺ᵐ⁾ | n, m ≥ 1 }
즉, n개의 a 뒤에 m개의 b가 오고, 다시 (n+m)개의 a가 이어지는 형태의 문자열입니다(n, m ≥ 1).
TM이 받아들일 수 있는 문자열의 예는 다음과 같습니다.
- abaa — n=1, m=1
- aabaaa — n=2, m=1
- abbaaa — n=1, m=2
- aaabaaaa — n=3, m=1
n=m=1일 때가 가장 짧은 문자열이며, 이때 최소한 a는 3개, b는 1개가 필요합니다.
접근 방법
머신은 먼저 n개의 a와 m개의 b를 모두 지나갑니다. 그런 다음 추가적인 a들을 만나면, 앞서 입력된 b와 a를 하나씩 z로 바꾸며 지워나갑니다. 마지막으로 더 이상 새로운 a가 없고 헤드가 첫 번째 입력 문자에 도달하면, 모든 문자가 올바르게 처리되었음을 의미합니다. 입력 문자열에 대해 단계별로 살펴보겠습니다.
상태 q0에서의 전이
δ(q0, a) → (q1, x, R): 상태 q0에서 읽은 문자가 a이면 상태 q1으로 전이하고, 해당 문자를 x로 바꾼 뒤 오른쪽으로 이동하여 다음 문자를 가리킵니다.
예: aabaaa → xabaaa (첫 번째 문자가 x로 바뀌고 헤드가 오른쪽으로 이동)
δ(q0, b) → (q3, x, R): 상태 q0에서 읽은 문자가 b이면 상태 q3으로 전이하고, 해당 문자를 x로 바꾼 뒤 오른쪽으로 이동합니다.
예: babaaa… → xabaaa… (첫 번째 문자가 x로 바뀌고 헤드가 오른쪽으로 이동)
여기서 x는 첫 번째 문자를 표시하는 데 사용됩니다.
상태 q1에서의 전이
δ(q1, a) → (q1, a, R): 상태 q1에서 읽은 문자가 a이면 상태 q1에 머무르고 오른쪽으로 이동합니다.
예: xaabaaa… → xaabaaa… (나머지 a에 대해서는 아무 작업 없이 오른쪽으로 이동)
δ(q1, b) → (q2, b, R): 상태 q1에서 읽은 문자가 b이면 상태 q2로 전이하고 오른쪽으로 이동합니다.
예: xaabaaa… → xaabaaa… (첫 번째 b를 만나면 q2로 이동)
상태 q2에서의 전이
δ(q2, b) → (q2, b, R): 상태 q2에서 읽은 문자가 b이면 상태 q2에 머무르고 오른쪽으로 이동합니다.
예: xaabbbaaa… → xaabbbaaa… (나머지 b에 대해서는 아무 작업 없이 오른쪽으로 이동)
δ(q2, z) → (q2, z, R): 상태 q2에서 읽은 문자가 z이면 상태 q2에 머무르고 오른쪽으로 이동합니다.
예: xaabaazz… → xaabaazz… (나머지 z에 대해서는 아무 작업 없이 오른쪽으로 이동)
δ(q2, a) → (q3, z, L): 상태 q2에서 읽은 문자가 a이면 해당 문자를 z로 바꾸고 상태 q3으로 전이한 뒤, 왼쪽으로 이동하여 이전 문자를 가리킵니다.
예: xaabaazz… → xaabazzz… (a를 z로 교체하고 왼쪽으로 이동)
상태 q3에서의 전이
δ(q3, z) → (q3, z, L): 상태 q3에서 읽은 문자가 z이면 상태 q3에 머무르고 왼쪽으로 이동합니다.
예: xaabzzzz… → xaabzzzz… (z에 대해서는 아무 작업 없이 왼쪽으로 이동)
δ(q3, b) → (q2, z, R): 상태 q3에서 읽은 문자가 b이면 해당 문자를 z로 바꾸고 상태 q2로 전이한 뒤 오른쪽으로 이동합니다. 모든 b를 z로 교체합니다.
예: xaabzzzz… → xaazzzzz… (b를 z로 교체하고 오른쪽으로 이동)
δ(q3, a) → (q2, z, R): 상태 q3에서 읽은 문자가 a이면 해당 문자를 z로 바꾸고 상태 q2로 전이한 뒤 오른쪽으로 이동합니다. 모든 a를 z로 교체합니다.
예: xaazzzz… → xaazzzzz… (a를 z로 교체하고 오른쪽으로 이동)
δ(q3, x) → (q4, z, R): 상태 q3에서 읽은 문자가 x이면 해당 문자를 z로 바꾸고 상태 q4로 전이한 뒤 오른쪽으로 이동합니다. 첫 번째 기호에 도달한 것입니다.
예: xzzzzzzz… → zzzzzzzz… (x를 z로 교체하고 오른쪽으로 이동)
상태 q4에서의 전이
δ(q4, z) → (q4, z, R): 상태 q4에서 읽은 문자가 z이면 상태 q4에 머무르고 오른쪽으로 이동합니다. 이 시점에는 모든 문자가 z입니다.
예: zzzzzzzz… → zzzzzzzz… (모든 z에 대해 아무 작업 없이 오른쪽으로 이동)
δ(q4, $) → (qf, $, R): 상태 q4에서 더 이상 남은 문자가 없으면 문자열의 끝에 도달한 것이며, 최종 상태 qf로 전이합니다. 이는 문자열이 받아들여졌음을 의미합니다.
예: zzzzzzzz$ → zzzzzzzz$ (문자열 끝 기호 $에 대해 아무 작업 없이 최종 상태로 이동)
다음 다이어그램은 해당 튜링 머신을 보여줍니다.
입력 예시
aabaaa
q0: aabaaa → q1: xabaaa → q1: xabaaa → q2: xabaaa → q3: xabzaa → q2: xazzaa
q2: xazzaa → q3: xazzza → q3: xazzza → q3: xazzza → q2: xzzzzza → q2: xzzzzza
q2: xzzzzza → q2: xzzzzza → q2: xzzzzza → q2: xzzzzzz → q3: xzzzzzz……..
q3: xzzzzzz → q3: xzzzzzz → q4: zzzzzzz → q4: zzzzzzz…….q4: xzzzzzz$ → qf: xzzzzzz$
최종 상태 qf에 도달했으므로 문자열 aabaaa는 받아들여집니다.