3.7 상태 전이 다이어그램을 통한 동작 시각화

1. 상태 전이 다이어그램의 정의

상태 전이 다이어그램(State Transition Diagram)은 튜링 기계의 전이 함수를 방향 그래프(Directed Graph)로 시각적으로 표현하는 방법이다. 이 다이어그램은 기계의 상태를 노드(Node)로, 상태 간의 전이를 방향 간선(Directed Edge)으로 표현하며, 기계의 전체 동작 규칙을 한눈에 파악할 수 있도록 시각화한다.

2. 다이어그램의 구성 요소

2.1 노드(Node)

각 노드는 기계의 하나의 상태 $q \in Q$ 를 나타낸다. 노드의 시각적 표기 관례:

시작 상태 $q_0$ : 화살표가 외부에서 노드를 가리키는 것으로 표시한다. 또는 노드에 “start” 레이블을 부착한다.
수락 상태 $q_{\text{accept}}$ : 이중 원(Double Circle)으로 표시한다.
거부 상태 $q_{\text{reject}}$ : 이중 원에 추가 표시를 하거나, 다이어그램에서 생략하기도 한다(명시적 거부 전이가 없는 경��).
일반 상태: 단일 원(Single Circle)으로 표시한다.

2.2 방향 간선(Directed Edge)

각 간선은 하나의 전이 규칙 $\delta(q, a) = (q', b, D)$ 를 나타낸다. 간선은 상태 $q$ 의 노드에서 상태 $q'$ 의 노드로 향하며, 간선에 다음의 레이블이 부착된다:

$a \rightarrow b, D$

이 레이블의 의미: “기호 $a$ 를 읽으면, $b$ 를 쓰고, 방향 $D$ 로 이동하며, 상태 $q'$ 로 전이한다.”

간선이 동일한 노드에서 출발하고 동일한 노드에 도착하는 경우(자기 루프, Self-Loop), 이는 상태가 변하지 않는 전이를 나타낸다.

레이블의 축약 표기

동일한 두 상태 사이에 여러 전이가 존재하는 경우, 간선을 하나로 합치고 레이블을 쉼표로 구분하여 나열할 수 있다. 예를 들어:

$\frac{a_1 \rightarrow b_1, D_1}{a_2 \rightarrow b_2, D_2}$

또는 간선 위에 “ $a_1 \rightarrow b_1, D_1 \;;\; a_2 \rightarrow b_2, D_2$ “로 병기한다.

3. 구체적 예시: 단항수의 짝수 판별기

입력이 단항수(Unary Number)로 표현된 자연수일 때, 그 수가 짝수인지 판별하는 튜링 기계를 상태 전이 다이어그램으로 기술한다.

입력: $1^n$ (기호 $1$ 이 $n$ 번 연속). $n$ 이 짝수이면 수락, 홀수이면 거부.

상태 집합: $Q = \{q_0, q_1, q_{\text{accept}}, q_{\text{reject}}\}$

$q_0$ : 짝수 개의 $1$ 을 읽은 상태 (현재까지 읽은 $1$ 의 수가 짝수)
$q_1$ : 홀수 개의 $1$ 을 읽은 상태

전이 함수:

$\delta(q_0, 1) = (q_1, 1, R)$ : $1$ 을 읽으면 홀수 상태로 전이, 오른쪽 이동
$\delta(q_1, 1) = (q_0, 1, R)$ : $1$ 을 읽으면 짝수 상태로 전이, 오른쪽 이동
$\delta(q_0, \sqcup) = (q_{\text{accept}}, \sqcup, R)$ : 공백을 만나면 짝수이므로 수락
$\delta(q_1, \sqcup) = (q_{\text{reject}}, \sqcup, R)$ : 공백을 만나면 홀수이므로 거부

다이어그램 구조:

$q_0 \xrightarrow{1 \rightarrow 1, R} q_1 \xrightarrow{1 \rightarrow 1, R} q_0$
$q_0 \xrightarrow{\sqcup \rightarrow \sqcup, R} q_{\text{accept}}$
$q_1 \xrightarrow{\sqcup \rightarrow \sqcup, R} q_{\text{reject}}$

$q_0$ 과 $q_1$ 사이에 양방향 간선이 존재하며, 기호 $1$ 을 읽을 때마다 두 상태를 번갈아 전이한다. 이 구조는 모듈러 연산(Modular Arithmetic) $n \mod 2$ 의 자동자적(Automaton-Based) 구현이다.

동작 추적(Trace)과 시각화

상태 전이 다이어그램 위에서의 동작 추적은 시작 노드에서 출발하여 간선을 따라 이동하는 경로(Path)로 시각화된다. 입력 $w = 1111$ 에 대한 위 기계의 동작 추적:

$q_0 \xrightarrow{1} q_1 \xrightarrow{1} q_0 \xrightarrow{1} q_1 \xrightarrow{1} q_0 \xrightarrow{\sqcup} q_{\text{accept}}$

$1$ 을 4번 읽은 후 $q_0$ 에 도달하고, 공백을 만나 수락 상태로 전이한다. 4는 짝수이므로 올바른 결과이다.

입력 $w = 111$ 에 대한 동작 추적:

$q_0 \xrightarrow{1} q_1 \xrightarrow{1} q_0 \xrightarrow{1} q_1 \xrightarrow{\sqcup} q_{\text{reject}}$

$1$ 을 3번 읽은 후 $q_1$ 에 도달하고, 공백을 만나 거부 상태로 전이한다. 3은 홀수이므로 올바른 결과이다.

복잡한 기계의 다이어그램

다수의 상태를 갖는 기계

상태 수가 증가하면 다이어그램의 복잡도가 증가한다. 이를 관리하기 위한 전략:

상태 그룹화(Grouping): 관련된 상태를 점선 박스로 묶어 기능적 모듈을 시각적으로 구분한다.
서브루틴 추상화(Subroutine Abstraction): 반복적으로 사용되는 상태 패턴을 하나의 블록으로 추상화하여 다이어그램의 복잡도를 줄인다.
계층적 표현(Hierarchical Representation): 전체 다이어그램을 상위 수준의 모듈 다이어그램과 하위 수준의 세부 다이어그램으로 분리한다.

자기 루프(Self-Loop)의 표현

동일한 상태에 머무르면서 테이프의 기호를 읽고 이동하는 동작은 자기 루프로 표현된다. 예를 들어, “상태 $q_3$ 에서 기호 $0$ 또는 $1$ 을 읽으면 해당 기호를 유지하고 오른쪽으로 이동하며 $q_3$ 에 머무른다“는 규칙은 $q_3$ 에서 $q_3$ 로의 자기 루프 간선으로 표현된다.

상태 전이 다이어그램의 형식적 정의

상태 전이 다이어그램은 레이블이 부착된 방향 그래프(Labeled Directed Graph) $G = (V, E, \lambda)$ 로 형식화된다:

$V = Q$ : 노드 집합은 상태 집합과 동일하다.
$E \subseteq Q \times Q$ : 간선 집합. $(q, q') \in E$ 이면 $q$ 에서 $q'$ 로의 전이가 존재한다.
$\lambda: E \rightarrow \mathcal{P}(\Gamma \times \Gamma \times \{L, R\})$ : 레이블 함수. 각 간선에 해당하는 전이의 읽기/쓰기/이동 정보를 부여한다.

유한 오토마타 다이어그램과의 관계

튜링 기계의 상태 전이 다이어그램은 유한 오토마타(Finite Automaton)의 상태 전이 다이어그램의 확장이다. 유한 오토마타에서 간선 레이블은 읽은 기호만을 포함하는 반면, 튜링 기계에서는 읽은 기호, 쓸 기호, 이동 방향의 세 가지 정보를 포함한다. 이 확장은 튜링 기계가 유한 오토마타에 비해 갖는 추가적 능력—테이프에 쓰기와 양방향 이동—을 반영한다.

상태 전이 다이어그램은 튜링 기계의 동작을 가장 직관적으로 파악할 수 있는 시각적 도구이며, 기계의 설계, 분석, 교육에서 필수적인 표현 방법이다.