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

NFA (Nondeterministic Finite Automata)

NFA

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

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

구분	DFA	NFA
전이 대상	단 하나의 상태 ($Q$)	상태들의 집합 ($2^Q$)
$\lambda$ 전이	불가능	가능 ($\Sigma \cup \{\lambda \}$)
함수 정의	$\delta :Q\times \Sigma =Q$	\delta : Q \times \Sigma \to Q$$\delta : Q \times (\Sigma \cup \{\lambda\}) = 2^Q
![[Pasted image 20260418004237.png	300]]

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

• trap state를 생략 가능하다

확장 전이 함수(${\delta }^{\ast }$)와 NFA의 특징 NFA에서 특정 스트링 $w$를 입력했을 때 도달할 수 있는 상태는 하나가 아니라 상태들의 집합으로 나타난다

• ${\delta }^{\ast }(q,w)$: 상태 $q$에서 스트링 $w$를 읽고 갈 수 있는 모든 가능한 상태들의 모임이다
• 특징:
  • 설계 편의성: DFA보다 그래프를 그리기가 훨씬 직관적이고 간단하다
  • 추적의 복잡성: 하지만 실제로 따라가려면 가능한 모든 경로(가지 수)를 다 계산해야 하므로 머릿속으로 시뮬레이션하기는 더 어렵다
  • DFA는 NFA의 일종이다

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

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

NFA의 DFA 전환

NFA와 DFA는 표현력(Power) 면에서 동일하다. 즉, 모든 NFA는 그와 동일한 언어를 인식하는 DFA로 바뀔 수 있다

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

람다($\lambda$) 전이 처리: ${\lambda }^{\ast }$ (람다 폐쇄)

• $\lambda$-closure(S): 상태 집합 $S$에서 입력 문자 없이 $\lambda$만 따라가서 도달할 수 있는 모든 상태의 집합이다
• 규칙: 어떤 심볼 $a$를 읽을 때, 사실상 다음 과정을 거친다
  • 현재 상태에서 갈 수 있는 모든 $\lambda$ 경로를 미리 다 간다
  • 그 상태들에서 실제 심볼 $a$를 읽고 이동한다
  • 이동한 후 도달한 곳에서 다시 $\lambda$로 갈 수 있는 곳을 다 간다

예시

• Final State가 포함된 state는 모두 표시한다

DFA 상태 최소화(Minimization)

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

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

상태 축소의 핵심 개념

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

구분 가능 (Distinguishable) 두 상태 $p$와 $q$에 대해, 어떤 스트링 $w$를 입력했을 때 한쪽은 수락 상태($F$)에 도달하고, 다른 한쪽은 비수락 상태($\notin F$)에 도달한다면, 두 상태는 스트링 $w$에 의해 구분 가능하다고 한다

구분 불가능 / 등가 (Indistinguishable / Equivalent) 모든 가능한 스트링 $w$에 대해 두 상태의 결과가 항상 같다면, 두 상태는 실질적으로 같은 역할을 하는 것이므로 하나로 합칠 수 있다

상태 축소 알고리즘

스트링의 길이 $|w|$를 늘려가며 상태를 분할하는 과정이다 1. $w=\lambda$ 가장 먼저 **수락 상태($F$)**와 비수락 상태($\notin F$)를 분리합니다. $\lambda$(공스트링)를 넣었을 때 바로 결과가 갈리기 때문이다

2. $|w|=다음심볼$ 각 그룹 내의 상태들이 특정 심볼을 받았을 때 서로 다른 그룹으로 가는지 확인한다

3. 반복 및 종료 더 이상 그룹이 쪼개지지 않을 때까지 반복한다. 이때 각 그룹이 최소화된 DFA의 새로운 상태가 된다