이 글에서는 언어 L = {wwr | w ∈ {0, 1}}를 인식하는 튜링 기계(Turing Machine)를 만드는 방법을 살펴봅니다. 이 언어는 0과 1이라는 두 개의 문자만으로 구성된 문자열을 다루며, w는 임의의 문자열이고 wr은 해당 문자열을 거꾸로 뒤집은 역순(reverse)을 의미합니다.
예를 들어 w = 10110이라면, wr은 01101이 됩니다. 따라서 튜링 기계는 z = 1011001101과 같은 형태의 문자열을 수용(accept)해야 합니다.
문제 해결 접근 방식
이 문제는 다음과 같은 단계별 방법으로 해결할 수 있습니다.
먼저 문자열의 첫 번째 심볼을 확인합니다. 첫 번째 심볼이 0이면 이를 y로 교체하고, 1이면 x로 교체합니다. 그다음 테이프의 끝까지 이동하여 마지막 심볼을 검사합니다. 마지막 심볼은 첫 번째 심볼과 반드시 같아야 하므로, 역시 그 값에 따라 x 또는 y로 교체합니다.
이후 다시 시작 지점 근처로 헤드를 되돌려, 아직 교체되지 않은 다음 심볼에 대해 동일한 과정을 반복합니다. 즉, 앞쪽에서 n번째 심볼을 교체할 때마다 뒤쪽에서 대응되는 n번째 심볼도 함께 교체하는 방식으로 진행됩니다.
핵심 포인트
wr은 w의 역순이므로 두 문자열의 길이는 항상 같다는 점을 기억해야 합니다. 따라서 앞쪽에서 n번째 심볼을 교체할 때마다 뒤쪽에서 정확히 대응되는 n번째 심볼을 교체하면 됩니다. 모든 심볼이 성공적으로 짝지어 교체되면 해당 문자열은 언어 L에 속하는 것으로 판단하고 수용합니다.
상태 전이 다이어그램
아래 다이어그램은 위에서 설명한 과정을 상태와 전이 규칙으로 표현한 것입니다.
