언어 L = {0ⁿ1ⁿ2ⁿ | n≥1}을 위한 튜링 기계
이 글에서는 언어 L = {0n1n2n | n ≥ 1}을 인식하는 튜링 기계(Turing Machine)를 설계하는 방법을 살펴봅니다. 이 언어는 0, 1, 2 세 가지 문자만으로 구성되며, 세 문자의 개수가 모두 동일한 문자열들의 집합을 의미합니다. 예를 들어 w = 000111222라면 0, 1, 2가 각각 3개씩 존재하므로 튜링 기계는 이 문자열을 수용(accept)합니다.
해결 접근 방식
이 문제는 마커(marker) 기호를 이용해 이미 처리한 문자를 표시해 가며 해결할 수 있습니다. 테이프의 왼쪽 끝에서 시작해 한 번에 한 문자씩 처리하며, 구체적인 동작 순서는 다음과 같습니다.
- 0 → x 치환: 문자열 맨 앞의 0 하나를 x로 바꿉니다.
- 1 → y 치환: 오른쪽으로 이동하며(이미 y로 바뀐 기호는 건너뜀) 아직 처리되지 않은 첫 번째 1을 찾아 y로 교체합니다.
- 2 → z 치환: 다시 오른쪽으로 이동해 첫 번째 2를 찾아 z로 바꾼 뒤, 왼쪽 방향으로 되돌아갑니다.
- x 위치로 복귀: 왼쪽으로 계속 이동해 x를 찾으면 한 칸 오른쪽으로 옮긴 뒤 위 과정을 반복합니다.
이 과정을 반복하다 보면 어느 시점에 x 바로 오른쪽에 y가 있는 상황, 즉 더 이상 치환할 0이 남아 있지 않은 지점에 도달하게 됩니다. 이때부터는 오른쪽 끝까지 이동하면서 남은 모든 기호가 y와 z뿐인지, 처리되지 않은 1이나 2가 없는지 검사합니다. 변환되지 않은 1 또는 2가 하나라도 남아 있다면 해당 문자열은 거부(reject)되고, 테이프의 끝을 나타내는 $에 도달할 때까지 모든 기호가 y와 z였다면 문자열은 수용됩니다.
동작 예시
입력이 001122일 경우를 생각해 보겠습니다. 첫 번째 사이클이 끝나면 x0y1z2가 되고, 두 번째 사이클을 거치면 xxyyzz가 됩니다. 이후 x 바로 뒤에서 y를 발견하면 검사 모드로 전환되어 오른쪽 끝까지 확인한 후 문자열을 수용합니다. 반면 00111222처럼 세 문자의 개수가 일치하지 않는 문자열은 검사 단계에서 변환되지 않은 기호가 발견되어 거부됩니다.
상태 전이 다이어그램(State Transition Diagram)
아래 다이어그램은 위에서 설명한 동작을 상태(state)와 전이(transition)의 형태로 표현한 것입니다.
