이 글에서는 언어 L = {AⁱBʲCᵏ | i < j < k, i ≥ 1}를 인식하는 튜링 기계(Turing Machine)를 만드는 방법을 살펴봅니다.
언어의 정의와 조건
이 언어는 오직 A, B, C 세 가지 문자만으로 구성된 문자열들을 포함합니다. 여기서 중요한 조건은 각 문자의 개수가 반드시 i < j < k 관계를 만족해야 한다는 것입니다. 즉, B의 개수가 A보다 많고, C의 개수는 다시 B보다 많아야 합니다.
예를 들어 w = AABBBBCCCCC인 경우를 생각해 보겠습니다. 이 문자열은 A가 2개, B가 4개, C가 5개로 구성되어 있으며, 2 < 4 < 5 조건을 충족하므로 튜링 기계는 이 문자열을 수용(accept)합니다.
문제 해결 접근 방식
이 문제를 해결하기 위해 다음과 같은 방식으로 접근합니다.
먼저 두 요소를 하나의 단위로 묶어 비교한 뒤, 각 기호의 개수 관계를 순차적으로 검사합니다. 즉, |A| < |B| < |C| 관계가 성립하는지 확인하는 것이 핵심입니다.
- B의 개수가 A보다 많고, C의 개수가 B보다 많으면 → 문자열을 수용합니다.
- 위 조건 중 하나라도 만족하지 않으면 → 문자열을 거부(reject)합니다.
실제 튜링 기계 구현에서는 일반적으로 읽은 기호를 X, Y, Z 같은 마커 기호로 덮어쓰는(marking) 방식을 사용하여 이미 확인한 문자의 개수를 추적하고, 테이프를 앞뒤로 이동하면서 세 기호의 개수를 짝지어 비교하게 됩니다.
상태 전이 다이어그램
아래 다이어그램은 위 언어를 인식하는 튜링 기계의 상태 전이(State Transition) 과정을 보여줍니다.
