이 글에서는 언어 L = {aⁱbʲcᵏ | i > j > k, k ≥ 1}를 인식하는 튜링 머신(Turing Machine)을 만드는 방법을 살펴봅니다. 이 언어는 오직 세 개의 문자 a, b, c로만 구성된 문자열들을 다루며, 각 문자의 개수가 엄격한 순서 관계를 만족해야 합니다. 즉, a의 개수(i)가 b의 개수(j)보다 많고, b의 개수(j)가 c의 개수(k)보다 많아야 하며, c는 최소 1개 이상 존재해야 합니다.
예를 들어 입력 문자열이 w = aaaaaabbbbccc라고 해봅시다. 여기서 a는 6개, b는 4개, c는 3개이므로 6 > 4 > 3이라는 조건을 충족합니다. 따라서 튜링 머신은 이 문자열을 정상적으로 수용(accept)하게 됩니다.
해결 접근 방식
이 문제는 문자열을 한 번에 판단하는 것이 아니라, 두 문자씩 짝지어 단계적으로 비교하는 방식으로 해결합니다.
- 1단계 — a와 b 비교: 하나의 a와 하나의 b를 짝지어 마킹하면서 개수를 비교합니다. 모든 b가 소진된 후에도 마킹되지 않은 a가 하나 이상 남아 있어야 합니다(i > j). a가 b보다 적거나 개수가 같다면 조건이 깨지므로 문자열은 거부됩니다.
- 2단계 — b와 c 비교: 다음으로 남은 b와 c를 같은 방식으로 짝지어 비교합니다. 모든 c가 소진된 후에도 마킹되지 않은 b가 하나 이상 남아 있어야 합니다(j > k).
정리하면, c의 개수가 앞서 비교에 사용된 (a, b) 쌍의 개수보다 많거나, b의 개수가 a의 개수보다 크거나 같은 경우에는 문자열이 수용되지 않습니다. 이 두 조건을 모두 통과한 경우에만 해당 문자열이 최종적으로 수용됩니다.
상태 전이 다이어그램
아래 그림은 위 규칙을 구현한 튜링 머신의 상태 전이 다이어그램입니다. 각 상태는 테이프 헤드의 좌우 이동과 마킹 동작(문자를 X, Y 등의 기호로 대체)을 정의하여 i > j > k라는 개수 관계를 체계적으로 검증합니다.
