[계산이론및오토마타] 2 NFA(Nondeterministic Finite Automata)

1. NFA (Nondeterministic Finite Automata)

NFA (비결정적 유한 인식기)

NFA는 DFA와 달리, 한 상태에서 동일한 입력 기호에 대해 여러 개의 상태로 전이하거나, 입력 없이도 상태를 옮길 수 있는 유연한 오토마타 모델이다

DFA와 NFA의 핵심 차이점 이 둘의 가장 큰 차이는 수학적 정의의 전이 함수 ($\delta$)에서 나타난다

구분	DFA	NFA
전이 대상	단 하나의 상태 ($Q$)	상태들의 집합 ($2^Q$)
$\lambda$ 전이	불가능	가능 ($\Sigma \cup \{\lambda \}$)
함수 정의	$\delta :Q\times \Sigma \to Q$	$\delta :Q\times (\Sigma \cup \{\lambda \})\to 2^Q$

1.1 $\lambda$-전이 (Lambda Transition)

입력 문자열을 전혀 소비하지 않고도 다음 상태로 이동할 수 있는 규칙이다. 복잡한 오토마타를 설계할 때 논리적 흐름을 단순하게 만들어 주는 강력한 도구이다

• Trap State 생략 가능: NFA에서는 특정 입력에 대해 갈 수 있는 전이가 정의되지 않은 경우 그대로 경로가 소멸(거부)되므로, DFA처럼 모든 입력에 대한 Trap State(Dead State)를 명시적으로 그릴 필요가 없다

1.2 확장 전이 함수(${\delta }^{\ast }$)와 NFA의 특징

NFA에서 특정 스트링 $w$를 입력했을 때 도달할 수 있는 상태는 하나가 아니라 상태들의 집합으로 나타난다

• ${\delta }^{\ast }(q,w)$: 상태 $q$에서 시작하여 스트링 $w$를 읽고 갈 수 있는 모든 가능한 상태들의 모임이다
• NFA의 주요 특징:
  • 설계 편의성: 사람의 직관에 더 가깝기 때문에 복잡한 조건의 언어라도 DFA보다 그래프를 그리기가 훨씬 직관적이고 간단하다
  • 추적의 복잡성: 하지만 실제로 경로를 따라가려면 가능한 모든 분기(Branch)를 다 계산해야 하므로 머릿속이나 컴퓨터 프로그램으로 시뮬레이션하기는 더 까다롭다
  • 포함 관계: 결정적 전이 역시 비결정적 전이의 특수한 경우이므로, 모든 DFA는 NFA의 일종이라고 볼 수 있다

1.3 NFA가 수락하는 언어 $L(M)$

$L(M)=\{w\in {\Sigma }^{\ast }:{\delta }^{\ast }(q_0,w)\cap F\ne \varnothing \}$

• 의미: 입력 가능한 모든 스트링($w\in {\Sigma }^{\ast }$) 중에서, 시작 상태($q_0$)에서 스트링 $w$를 따라갔을 때 도달 가능한 여러 상태들의 집합 중 단 하나라도 수락 상태($F$)가 포함되어 있으면 그 스트링은 수락(Accept)된다
• 즉, 가능한 여러 갈래의 길 중 단 하나의 경로라도 성공(수락 상태 도달)에 이르면 NFA는 해당 스트링을 받아들인다

---

2. NFA의 DFA 변환

표현력의 동등성

NFA와 DFA는 표현력(Power) 면에서 완전히 동일합니다. 즉, 모든 NFA는 그와 동일한 언어를 인식하는 DFA로 변환할 수 있다

부분집합 구성 (Subset Construction) 핵심 아이디어 NFA는 한 번에 여러 상태에 있을 수 있다. DFA는 이 ‘상태들의 집합’ 자체를 하나의 새로운 상태로 묶어서 간주하여 “현재 NFA가 가질 수 있는 모든 가능성”을 결정적으로 추적한다

2.1 람다($\lambda$) 전이 처리: $\lambda$-closure (람다 폐쇄)

• $\lambda$-closure($S$): 상태 집합 $S$에서 입력 기호 없이 $\lambda$-전이만 따라가서 도달할 수 있는 모든 상태의 집합이다(자기 자신도 포함)
• 입력 처리 규칙: 어떤 심볼 $a$를 읽을 때, NFA는 사실상 다음 세 단계를 거친다
  1. 현재 상태에서 갈 수 있는 모든 $\lambda$ 경로를 미리 전부 따라간다
  2. 확보된 상태들에서 실제 입력 심볼 $a$를 읽고 이동한다
  3. 이동 후 도달한 곳에서 다시 $\lambda$로 갈 수 있는 곳을 전부 찾아 포함시킨

• 수락 상태 결정: 변환된 DFA의 상태들(즉, NFA 상태들의 부분집합) 중에서, 기존 NFA의 수락 상태($F$)가 단 하나라도 포함된 집합은 모두 변환된 DFA의 수락 상태가 된다

---

3. DFA 상태 최소화 (Minimization)

NFA를 DFA로 변환하면 상태 개수가 최대 $2^n$개까지 폭발적으로 늘어날 수 있다. 상태 최소화는 이렇게 비대해진 DFA에서 불필요한 상태를 제거하여, 동일한 언어를 인식하는 가장 작은 형태의 상태 기계를 만드는 과정이다

전처리: 도달 불가능한 상태 제거 알고리즘을 시작하기 전, 시작 상태($q_0$)에서 어떤 입력 스트링을 통해서도 절대 갈 수 없는 상태(Unreachable States)를 찾아 삭제한다. 이들은 언어 인식 결과에 아무런 영향을 주지 않는 유령 상태들이다

3.1 상태 축소의 핵심 개념

DFA의 상태 개수를 줄이기 위해서는 임의의 두 상태가 서로 구분 가능한가(Distinguishable), 아니면 구분 불가능한가(Indistinguishable)를 판별해야 한다

• 구분 가능 (Distinguishable): 두 상태 $p$와 $q$에 대해, 어떤 스트링 $w$를 입력했을 때 한쪽은 수락 상태($F$)에 도달하고, 다른 한쪽은 비수락 상태($\notin F$)에 도달한다면, 두 상태는 스트링 $w$에 의해 구분 가능하다고 한다
• 구분 불가능 / 등가 (Indistinguishable / Equivalent): 모든 가능한 스트링 $w$에 대해 두 상태의 최종 도달 결과(수락 여부)가 항상 같다면, 두 상태는 실질적으로 똑같은 역할을 하는 것이므로 하나로 합칠 수 있다

3.2 상태 축소(분할) 알고리즘

검사할 스트링의 길이 $|w|$를 늘려가며 상태들의 그룹을 쪼개는 과정(Partitioning)이다

1. $w=\lambda$ (길이 0): 가장 먼저 모든 상태를 수락 상태($F$) 그룹과 비수락 상태($\notin F$) 그룹 두 개로 크게 분리한다. 입력이 없을 때(공스트링) 이미 수락 여부가 갈리기 때문이다
2. $|w|=1$ (입력 심볼 확인): 같은 그룹 내에 있는 상태들이 특정 기호(예: 0 또는 1)를 입력받았을 때 서로 다른 그룹으로 전이되는지 확인한다. 만약 도착하는 그룹이 다르다면, 이 상태들은 서로 구분 가능하므로 다른 그룹으로 쪼갠다(분할)
3. 반복 및 종료: 모든 입력 기호에 대해 더 이상 그룹이 쪼개지지 않을 때까지 2번 과정을 반복한다. 분할이 완전히 끝나면, 최종적으로 묶여있는 각 그룹이 최소화된 DFA의 새로운 단일 상태가 된다