이번 글에서는 언어 L = {AⁱBʲCᵏ | i × j = k; i, j, k ≥ 1}를 인식하는 튜링 머신(Turing Machine)을 설계하는 방법을 살펴보겠습니다. 이 언어는 문자 A, B, C 세 가지만으로 구성된 문자열들의 집합으로, C의 개수(k)가 A의 개수(i)와 B의 개수(j)를 곱한 값과 정확히 일치해야 한다는 규칙을 따릅니다.
예를 들어 문자열 w = AABBBBCCCCCCCC를 생각해 볼 수 있습니다. 이 문자열은 A가 2개, B가 4개, C가 8개로 이루어져 있고 2 × 4 = 8이 성립하므로, 튜링 머신은 이 문자열을 수용(accept)합니다.
핵심 아이디어: 마킹(Marking) 기법
이 문제는 테이프 위의 기호를 하나씩 표시해 가며 개수를 세는 방식으로 해결합니다. 하나의 A를 처리할 때마다 모든 B 각각에 대해 하나의 C를 짝지어 소모합니다. 이 과정을 모든 A에 대해 반복한 뒤, 더 이상 남는 C가 없다면 곱셈 조건 i × j = k가 만족된 것으로 판정합니다.
단계별 동작 과정
- A 마킹: 먼저 하나의 A를 x로 교체하고 오른쪽으로 이동합니다. 그런 다음 나머지 모든 A를 건너뛰며 계속 오른쪽으로 진행합니다.
- B와 C 매칭: 헤드가 첫 번째 B에 도달하면 그 B를 y로 교체하고, 중간에 있는 모든 B를 건너뛰며 오른쪽으로 이동합니다. 그다음 방금 교체한 B에 대응하는 하나의 C를 z로 바꾼 뒤 왼쪽으로 되돌아갑니다.
- 왼쪽 복귀: 왼쪽으로 이동하면서 경로상의 모든 z와 B를 건너뜁니다.
- y 위치 확인: 포인터가 가장 최근에 표시한 y에 도달하면 오른쪽으로 이동합니다.
- 분기 처리: 포인터가 B를 가리키고 있다면 2~4단계를 반복합니다. 반대로 z를 가리키고 있다면(현재 A에 대한 B 처리가 모두 끝났다는 의미) 왼쪽으로 이동하면서 모든 y를 다시 B로 복원하고, A는 건너뛰며 진행합니다.
- x 위치 확인: 포인터가 가장 최근의 x에 도달하면 오른쪽으로 이동합니다.
- 반복 여부 판단: 포인터가 아직 A를 가리키고 있다면 위의 전체 과정을 반복합니다. 더 이상 A가 없고 헤드가 y에 위치해 있다면, 모든 y와 z를 건너뛰며 오른쪽으로 이동합니다.
- 최종 수용: 입력의 끝을 나타내는 $ 기호에 도달하면 왼쪽으로 이동합니다. 이 시점에서 문자열은 최종적으로 수용됩니다.
상태 전이 다이어그램
아래 상태 전이 다이어그램은 앞서 설명한 동작 과정을 각 상태(state)와 전이(transition)의 형태로 표현한 것입니다. 다이어그램을 따라가 보면 마킹 기법이 실제 튜링 머신의 상태 변화로 어떻게 구현되는지 명확하게 이해할 수 있습니다.
