언어 L = {ww | w ∈ {0,1}}란?
이번 글에서는 언어 L = {ww | w ∈ {0,1}}를 인식하는 튜링 기계(Turing Machine)를 만드는 방법을 살펴보겠습니다. 이 언어는 0과 1 두 개의 문자만으로 구성된 문자열 w가 자기 자신과 한 번 더 연결된 형태, 즉 ww의 집합을 의미합니다. 예를 들어 w = 10110이라면, 튜링 기계는 z = 1011010110이라는 입력 문자열을 받아들여야 합니다.
문제 해결 접근 방식
1단계: 문자열의 중간 지점 찾기
가장 먼저 할 일은 문자열의 중간 지점(midpoint)을 찾는 것입니다. 왼쪽 끝에서 0은 X로, 1은 Y로 하나씩 변환해 나가고, 오른쪽 끝에서도 같은 작업을 반복하며 안쪽으로 이동합니다. 이 과정을 계속 진행하다 보면 모든 0과 1이 X와 Y로 바뀌는 순간이 오는데, 바로 그 시점이 문자열의 중간입니다. 이렇게 첫 번째 목표가 완성됩니다.
2단계: 왼쪽 절반 복원하기
다음으로 중간 지점 왼쪽에 있는 모든 X와 Y를 다시 0과 1로 되돌립니다. 그러면 문자열의 첫 번째 절반은 0과 1의 형태가 되고, 두 번째 절반은 X와 Y의 형태로 유지됩니다.
3단계: 앞부분과 뒷부분 대조하기
이제 문자열의 맨 처음부터 다시 시작합니다. 0을 만나면 X로 변환한 뒤 오른쪽으로 이동하여 두 번째 절반에 도달할 때까지 진행합니다. 거기서 대응되는 X를 발견하면 공백(blank, B)으로 바꿉니다. 그런 다음 헤드를 왼쪽으로 되돌려 첫 번째 절반에서 X 또는 Y로 표시된 기호를 찾습니다. 그 기호 바로 오른쪽에 있는 0 또는 1을 각각 X 또는 Y로 변환하고, 동시에 두 번째 절반에서 그것과 짝을 이루는 X 또는 Y를 공백(B)으로 바꿉니다.
4단계: 반복 및 수용·거부 판정
위 과정을 반복하여 문자열 왼쪽 부분의 모든 기호가 X와 Y로, 오른쪽 부분의 모든 기호가 공백으로 변환될 때까지 진행합니다.
- 한쪽 절반이 완전히 변환되었는데도 다른 쪽 절반에 변환되지 않은 기호가 남아 있다면 → 거부(reject)
- 첫 번째 절반의 0 또는 1에 대응하는 X 또는 Y를 두 번째 절반에서 찾지 못했다면 → 거부(reject)
- 모든 기호가 성공적으로 짝지어져 소진되었다면 → 수용(accept)
참고로 L = {ww | w ∈ {0,1}*}는 문맥 자유 언어(context-free language)에는 속하지 않지만, 위와 같은 알고리즘을 통해 튜링 기계로는 충분히 판정 가능(decidable)하다는 점이 흥미롭습니다.
상태 전이 다이어그램
아래는 위에서 설명한 알고리즘을 실제로 구현한 튜링 기계의 상태 전이 다이어그램(state transition diagram)입니다. 각 상태와 전이 규칙이 어떻게 기호 변환 및 헤드 이동을 처리하는지 확인해 보세요.
