NFA — 비결정론적 유한 오토마타

DFA에서는 하나의 상태에서 하나의 입력에 대해 정확히 하나의 다음 상태만 존재했다. NFA는 이 제약을 풀어, 하나의 입력에 대해 여러 상태로 동시에 전이할 수 있다. 더 강력한 모델처럼 보이지만, 실제 계산 능력은 DFA와 동일하다.

이 포스트에서 다루는 내용

NFA(Non-deterministic Finite Automata)의 구조와 accept 조건
한 상태에서 같은 입력에 여러 상태로 동시에 전이하는 비결정성의 의미
Powerset Construction — NFA를 DFA로 변환하는 방법
NFA와 DFA의 계산 능력이 본질적으로 동일하다는 결론

DFA vs NFA

NFA(Non-deterministic Finite Automata)는 비결정론적 유한 오토마타 다. DFA와 구조는 유사하지만, 하나의 상태에서 동일한 입력에 대해 여러 상태로 동시에 전이할 수 있다는 점이 근본적으로 다르다. “비결정론적”이란 다음 상태가 하나로 결정되지 않는다는 의미다.

NFA의 구조

NFA도 DFA와 마찬가지로 다섯 가지 요소의 튜플로 정의한다.

M = (Q,\ \Sigma,\ q_0,\ F,\ \Delta)

$Q$ : State들의 집합
$\Sigma$ : Alphabet
$q_0$ : Initial state
$F$ : Accepting state들의 집합
$\Delta$ : Transition relation

\Delta: Q \times \Sigma \to \mathcal{P}(Q)

DFA의 transition function $\delta: Q \times \Sigma \to Q$ 는 항상 정확히 하나의 다음 상태를 반환한다. 반면 NFA의 $\Delta$ 는 가능한 다음 상태들의 집합 을 반환한다.

예를 들어 $\Delta(q, a) = \{r, s\}$ 이면, 상태 $q$ 에서 $a$ 를 읽었을 때 $r$ 로도, $s$ 로도 전이할 수 있다. 만약 $\Delta(q, a) = \emptyset$ 이면 해당 경로는 막힌다(dead end).

ε-전이(Epsilon Transition): NFA의 확장 버전으로, 입력을 소비하지 않고도 상태를 전이할 수 있는 ε-NFA 가 있다. $\Delta: Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)$ 로 정의하며, 입력 없이 자유롭게 다른 상태로 이동할 수 있다. ε-NFA도 DFA로 변환할 수 있어 계산 능력은 동일하다. 다만 변환에 한 단계가 더 붙는다. 부분집합을 만들 때마다 ε만 따라가서 더 도달할 수 있는 상태를 모두 끌어모으는 ε-폐포(ε-closure) 를 취해야 한다. 아래에서 다루는 Powerset Construction은 이 단계가 없는 형태이며, 이 글에서 NFA라고 하면 ε-전이 없는 기본 NFA를 가리킨다.

NFA의 비결정성: 동시에 여러 경로

NFA 분기 동작 — 상태 q에서 입력 a 하나로 상태 r과 s 두 갈래가 동시에 열리고, 한쪽은 accepting state에 닿고 다른 쪽은 dead end로 막힌다. 하나라도 닿았으므로 전체는 accept

NFA는 같은 입력에서 여러 경로를 동시에 탐색한다. 각 분기점에서 가능한 모든 다음 상태로 동시에 이동하며, 경로 중 하나라도 accepting state에 도달하면 accept한다.

Accept 조건

가능한 경로 중 하나라도 accepting state에 도달하면 accept한다.
모든 경로가 dead end이거나 non-accepting state에서 끝날 때만 reject한다.

이 성질 때문에 NFA를 시뮬레이션하면 마치 “정답 경로를 미리 알고” 이동하는 것처럼 보이기도 한다. 실제 시뮬레이션에서는 가능한 모든 경로를 동시에 탐색하여 하나라도 accept하는지 확인한다.

NFA와 DFA의 관계: Powerset Construction

NFA는 직접 구현하기보다 이론적 도구 로서 유용하다. DFA보다 설계가 간결하고 직관적이기 때문에, 복잡한 언어를 NFA로 먼저 설계한 뒤 DFA로 변환하는 방식을 사용한다.

아래는 4개의 state를 가진 NFA 예시다.

4개 상태를 가진 NFA 예시 — '101'을 부분 문자열로 포함하는 문자열을 인식한다. 상태 1과 4는 0,1 자기 루프를 갖고, 1에서 1을 읽어 2로, 2에서 0을 읽어 3으로, 3에서 1을 읽어 accepting state인 4로 간다

모든 NFA는 Powerset Construction(부분집합 구성법) 을 통해 동등한 DFA로 변환할 수 있다. NFA의 state 집합을 $Q$ 라 하면, 변환된 DFA의 각 state는 $Q$ 의 부분집합 $\mathcal{P}(Q)$ 의 원소가 된다.

Powerset Construction 한 걸음 — NFA가 상태 1과 3에 동시에 있을 때 입력 1을 주면 상태 1은 1,2로 상태 3은 4로 가고, 두 집합의 합집합인 1,2,4가 변환된 DFA의 단일 상태가 된다

이 NFA를 DFA로 변환하면 최대 $2^4 = 16$ 개의 state가 필요하다.

실제로는 도달 불가능한 state가 있어 16개보다 적을 수 있지만, 최악의 경우 상태 수는 지수적( $2^n$ )으로 증가한다.

변환 예시

NFA가 state 1과 3에 동시에 있는 상황을 DFA의 state $\{1, 3\}$ 으로 표현한다.

입력 1이 들어올 경우:

state 1에서 1 → $\{1, 2\}$
state 3에서 1 → $\{4\}$
합집합: 다음 DFA state $= \{1, 2, 4\}$

입력 0이 들어올 경우:

state 1에서 0 → $\{1\}$
state 3에서 0 → $\emptyset$
합집합: 다음 DFA state $= \{1\}$

변환된 DFA는 다음과 같이 구성된다.

항목	값
Initial state	$\{1\}$ (NFA의 initial state만 포함)
Accepting states	NFA의 accepting state(state 4)를 원소로 포함하는 모든 부분집합

\{4\},\ \{1,4\},\ \{2,4\},\ \{3,4\},\ \{1,2,4\},\ \ldots

state 4를 고정하고 나머지 세 state를 넣거나 빼는 경우의 수이므로, accepting state는 모두 $2^3 = 8$ 개다.

결론: Class NFA = Class DFA

모든 NFA는 Powerset Construction으로 동등한 DFA로 변환할 수 있다. 따라서 NFA가 accept하는 모든 언어는 DFA도 accept할 수 있고, 그 역도 성립한다.

\text{Class NFA} = \text{Class DFA}

쉽게 말하면

NFA는 "여러 가능성을 동시에 시도하는 DFA"지만, 결국 풀 수 있는 문제의 범위는 DFA와 같다. NFA의 모든 동시 탐색 경로를 DFA의 상태 조합으로 표현할 수 있기 때문이다. NFA는 설계를 쉽게 해주는 도구이지, 더 강력한 기계가 아니다.

핵심 결론: 표현력은 같지만 설계 감각이 다르다

NFA와 DFA는 인식할 수 있는 언어(Regular Languages)가 완전히 동일하다.
NFA는 DFA보다 설계하기 쉽고 직관적이지만, 더 강력한 모델이 아니다.
DFA로 풀 수 없는 문제(예: $L_5 = \{0^i1^i\}$ )는 NFA로도 풀 수 없다.

다음 포스트

DPDA와 NPDA — 스택을 가진 오토마타 — DFA에 스택을 추가하면 무엇이 달라질까? DPDA와 NPDA의 계산 능력 차이를 분석하고, 스택 2개로 튜링 머신을 시뮬레이션하는 원리를 살펴본다.