DFA, NFA and conversion ᓚᘏᗢ

1. DFA

DFA (Deterministic Finite Automaton)

= "결정적 유한 상태 오토마타"

한 입력에 대해 딱 하나의 상태로만 이동 가능!

길 잃는 거 없이 한 길만 쭉 가는 우직한 기계야~

오빠처럼 생각 없이 정해진 루트만 걷는 그런 느낌?♡

DFA의 구성요소

M = (Q, Σ, δ, q₀, F)

구성 요소 설명

Q	유한한 상태 집합
Σ	입력 알파벳 집합
δ	전이 함수: Q × Σ → Q (한 상태만 나와야 함!)
q₀	시작 상태
F	종료 상태들의 집합

DFA의 특징

항목 설명 비유 (오빠 스타일♡)

결정성	하나의 입력에 대해 오직 하나의 다음 상태만	오빠가 아무리 해도 여자친구는 생기지 않아, 딱 하나도 안 생겨~
전이 함수 δ	완벽히 정의되어 있어야 함 (어떤 입력도 빠짐없이)	오빠처럼 대답 못 하면 버그야ㅋㅋ
No ε-transition	입력 없이 상태 못 바꿈	오빠는 침묵해봤자 아무 일도 안 생겨♡
경로는 오직 하나	모든 입력에 대해 경로 유일	그래서 계산 흐름이 예측 가능하고 안전함

DFA 예시

상태 집합 Q = {q1, q2, q3}
입력 알파벳 Σ = {0, 1}
시작 상태는 q1
종료(accepting) 상태는 q2
전이 함수 δ는 다음과 같아

δ	0	1
q1	q1	q2
q2	q3	q2
q3	q2	q2

입력 문자열이 01011이라면?

한 글자씩 착착 계산 들어간다♡

δ(q1, 0) = q1
δ(q1, 1) = q2
δ(q2, 0) = q3
δ(q3, 1) = q2
δ(q2, 1) = q2

🎉 최종 도달 상태는 q2!

이건 바로 accepting 상태, 즉 입력 01011은 DFA가 인식해주는 문자열이란 말이지~

와~ 오빠 인생에선 이런 인정 받는 순간 보기 힘든데, 여기선 겨우 받아냈네?ㅋㅋ 기특하긴 해♡

❌ 수락되지 않는 입력 예시

1. 최종 상태가 q1인 경우: 입력 = 00

δ(q1, 0) = q1
δ(q1, 0) = q1
결과 상태 q1 = 수락 아님!

→ 이건 그냥 시작 상태에서 제자리걸음하다가 지쳐 쓰러진 오빠 느낌이야♡

2. 최종 상태가 q3인 경우: 입력 = 01010

δ(q1, 0) = q1
δ(q1, 1) = q2
δ(q2, 0) = q3
δ(q3, 1) = q2
δ(q2, 0) = q3

→ 최종 상태: q3 = 수락 상태 아님!

오빠처럼 뱅글뱅글 돌다가 결국 목적지 못 찾고 버려지는 그런 느낌이랄까?♡ 슬프다... 후우~

무조건 마지막 글자가 1이면 q1 상태 도달 → Accept

오빠처럼 아무 말 없이 끝나면 바로 Reject♡

DFA 작동 원리

시작 상태 q₀부터 출발
입력 문자열의 각 글자를 읽으면서 상태 이동
문자열 끝났을 때 현재 상태가 F에 있으면 accept, 아니면 reject

DFA는 엄격하고 예측 가능한 기계,

NFA는 자유롭고 선택이 많은 기계야.

근데 결국 둘 다 표현할 수 있는 언어는 똑같아♡

2. NFA

푸흡ㅋㅋ 드디어 DFA 따위는 오빠한테 너무 단단해서 포기하고 NFA로 왔네?♡

좋아~ 오빠 같은 허접이 좀 더 자유롭게 길 잃을 수 있는 세계, 비결정적 유한 오토마타의 매운맛을 맛보게 해줄게~♡

NFA란?

NFA (Nondeterministic Finite Automaton)

= "비결정적 유한 상태 오토마타"

오빠가 길을 걷다 갈림길 만나면 멈칫할 텐데, NFA는 그런 거 안 해~ 그냥 다 가버려ㅋㅋㅋ 그게 바로 NFA의 간지♡

NFA의 형식적 정의

M = (Q, Σ, δ, q₀, F)

구성 요소 설명

Q	상태들의 유한 집합
Σ	입력 알파벳 집합
δ	전이 함수: δ: Q × (Σ ∪ {ε}) → P(Q)
q₀	시작 상태
F	최종 상태(들)의 집합

오빠 주의~ DFA랑 달리 δ 결과가 집합(P(Q))이야!

하나가 아니라 여러 개의 상태로 갈 수 있으니까~♡

전이 유형

유형	설명	비유
Unique	하나의 입력에 하나의 상태로 전이 (DFA 스타일)	오빠가 아는 사람 하나밖에 없을 때처럼... 슬퍼ㅠ
Multiple	하나의 입력으로 여러 상태로 이동 가능	오빠가 카톡 보내도 모두 차단당하는 그런 느낌♡
No Transition	입력에 대해 전이 불가능 → dead end	읽씹당하는 오빠 그 자체ㅋ
ε-Transition	입력 없이도 상태 전이 가능	아무 말 안 했는데 분위기 바뀌는 상황ㅋㅋ

DFA랑 NFA의 차이

요소	DFA	NFA
전이	Unique	Multiple, 입력 없이도(ε-transition) 가능
결정성	완전 결정적	비결정적, 즉 운명처럼 복수 선택 가능♡
컴퓨팅 방식	딱 한 경로만 탐색	가능한 모든 경로 동시에 시도
실제 동작	구현 쉬움	시뮬레이션이나 변환 필요

요건 무조건 외워~ 오빠 시험에 나오면 무조건 맞아야지ㅋㅋ

NFA 작동 예시

q₁: 시작 상태
q₄: 종료(accepting) 상태 (double circle!)
중간에 q₂ → q₃로 ε-transition(입력 없이 넘어감!) 존재함

상태	입력	이동
q₁	0, 1	q₁ (loop)
q₁	1	q₂
q₂	0	q₃
q₂	ε	q₃
q₃	1	q₄
q₄	0, 1	q₄ (loop)

첫 번째 설명: 0110은 인식됨!

오빠, 여기선 NFA니까 가능한 경로 중 하나라도 Accept 상태로 가면 OK야♡

입력: 0110

0: q₁ (loop)
1: q₁ → q₂
1: q₂ → ε → q₃ → 1 → q₄
0: q₄ (loop)

q₁ → q₁ → q₂ → q₃ → q₄ → q₄

q₄는 accepting 상태니까 → 이 문자열 "0110"은 accept!!

두 번째 설명: "1"은 reject됨!

오빠, 이제 반례 보자♡

q₁에서 1 입력 → q₁ (loop 가능), 또는 q₂로 갈 수 있음
q₂는 다음 입력 없고, q₄ 도달하려면 최소한 0 또는 ε, 그리고 1이 더 필요해

즉, 현재 가능한 상태들 = {q₁, q₂, q₃}

근데 아직 q₄에는 도달 못 했고, 입력은 다 끝났음

q₄에 도달 못함 → Reject!

"0110" → 수락됨: q₄까지 도달 가능한 경로 존재
"1" → 거절됨: 입력 다 써도 q₄에 못 감

NFA는 이게 최고야. 오빠처럼 '될까?' 싶은 경로도 그냥 시도해보는 쿨한 기계지♡

그리고 하나라도 성공하면 그냥 받아줘~ 오빠 인생에도 이런 관대함 좀 있었으면 좋겠다ㅋ

왜 NFA가 쓸모 있음?

DFA보다 설계가 간단함
직관적이고 복잡한 조건도 쉽게 표현 가능
표현력은 DFA와 같음 → 정규 언어만 인식
필요하면 DFA로 변환 가능 → subset construction

Equivalence of NFA and DFA

모든 NFA는 동등한 DFA로 바꿀 수 있음

변환 요소	설명
Q′	DFA의 상태 = NFA 상태의 부분집합들 (2^Q)
q₀′	ε-closure({q₀})
δ′(R, a)	각 상태 r ∈ R에 대해 δ(r, a) → 그 결과에 ε-closure 적용
F′	종료 상태가 포함된 집합 R들 전체

3. NFA->DFA 변환

"NFA의 모든 가능성을 DFA가 '기억'하게 만드는 작업이야"

아이디어

NFA는 입력 하나에 여러 개의 상태로 갈 수 있지?
그래서 DFA는 그 모든 상태 집합을 하나의 상태처럼 다루는 거야.
즉, "현재 DFA의 상태 = NFA의 가능한 상태들의 집합" 이라는 뜻이야~

공식적인 변환 단계

가자, 오빠 정신 바짝 차리고 따라와봐♡

Step 1: DFA의 상태 집합 만들기

NFA의 상태가 Q라면, DFA의 상태는 Q의 모든 부분집합 (power set)
왜? NFA는 동시에 여러 상태에 있을 수 있으니까, 그걸 다 커버해야 해♡
→ DFA는 최대 2ⁿ개의 상태를 가질 수 있음 (n은 NFA 상태 수)

Step 2: 시작 상태 설정

NFA의 시작 상태 q0에서 ε-transition으로 도달 가능한 모든 상태
→ DFA의 시작 상태는 이 ε-closure({q0})!

Step 3: 전이 함수 만들기

DFA 상태 S가 있고, 입력 기호 a가 들어오면:
1. S에 있는 각 상태에서 a로 갈 수 있는 NFA 상태들을 모음
2. 그 상태들에 대해 ε-closure를 적용
3. 그게 DFA에서 a에 대한 다음 상태가 됨!

Step 4: 종료 상태 지정

DFA 상태들 중에 NFA의 종료 상태를 포함하는 집합이 있으면
그 집합을 DFA의 종료 상태로 지정!

NFA->DFA 변환 예시

기억해둬, 오빠:

DFA는 상태가 단 하나로만 전이되고,

ε-transition은 존재하지 않기 때문에

ε-closure(ε-닫힘)을 먼저 구해서 모든 상태를 '덩어리'로 만들어야 해♡

Step 1: 상태 정의 복습

상태 집합 Q = {q₁, q₂, q₃, q₄}

입력 기호 Σ = {0, 1}

시작 상태 q₁, 종료 상태 F = {q₄}

δ	0	1	λ
q₁	{q₁}	{q₁, q₂}	∅
q₂	{q₃}	∅	{q₃}
q₃	∅	{q₄}	∅
q₄	{q₄}	{q₄}	∅

Step 2: ε-Closure 계산

상태 ε-closure

q₁	{q₁}
q₂	{q₂, q₃}
q₃	{q₃}
q₄	{q₄}

오케이~ 이제 이걸 기반으로 DFA 상태들 만들어줄게.

각 DFA 상태는 NFA 상태들의 집합으로 표현돼! 💡

Step 3: DFA 상태 생성 및 전이

DFA 상태 A = {q₁} ✅ 시작 상태

입력 0:
- δ(q₁, 0) = {q₁}
- ε-closure({q₁}) = {q₁} → 상태 A로!
입력 1:
- δ(q₁, 1) = {q₁, q₂}
- ε-closure({q₁, q₂}) = {q₁, q₂, q₃} → 상태 B

DFA 상태 B = {q₁, q₂, q₃}

입력 0:
- q₁ → {q₁}, q₂ → {q₃}, q₃ → ∅
- → 합집합 = {q₁, q₃}
- ε-closure = {q₁, q₃} → 상태 C
입력 1:
- q₁ → {q₁, q₂}, q₂ → ∅, q₃ → {q₄} → 전체 = {q₁, q₂, q₄}
- ε-closure = {q₁, q₂, q₃, q₄} → 상태 D

DFA 상태 C = {q₁, q₃}

입력 0: q₁ → {q₁}, q₃ → ∅ → {q₁} → 상태 A
입력 1: q₁ → {q₁, q₂}, q₃ → {q₄}→ 상태 D
→ {q₁, q₂, q₄} → ε-closure = {q₁, q₂, q₃, q₄}

DFA 상태 D = {q₁, q₂, q₃, q₄} ✅ 수락 상태! (q₄ 포함)

입력 0:
- q₁ → {q₁}, q₂ → {q₃}, q₃ → ∅, q₄ → {q₄}
- → {q₁, q₃, q₄} → 상태 E
입력 1:
- q₁ → {q₁, q₂}, q₃ → {q₄}, q₄ → {q₄}
- → {q₁, q₂, q₄} → ε-closure = {q₁, q₂, q₃, q₄} → D

DFA 상태 E = {q₁, q₃, q₄} ✅ 수락 상태

입력 0: q₁ → {q₁}, q₄ → {q₄} → {q₁, q₄} → 상태 F
입력 1: q₁ → {q₁, q₂}, q₃ → {q₄}, q₄ → {q₄}
→ {q₁, q₂, q₄} → ε-closure = D

DFA 상태 F = {q₁, q₄} ✅ 수락 상태

입력 0: q₁ → {q₁}, q₄ → {q₄} → F
입력 1: q₁ → {q₁, q₂}, q₄ → {q₄} → {q₁, q₂, q₄} → D

DFA 상태	포함된 NFA 상태들	0 →	1 →	종료 상태
A	{q₁}	A	B	❌
B	{q₁, q₂, q₃}	C	D	❌
C	{q₁, q₃}	A	D	❌
D	{q₁, q₂, q₃, q₄}	E	D	✅
E	{q₁, q₃, q₄}	F	D	✅
F	{q₁, q₄}	F	D	✅

오빠용 핵심 요약♡

이 NFA는 1이 나오고, ε 또는 0을 통해 q₃ → 1 → q₄ 도달하면 accept 되는 구조야.

그걸 DFA는 상태 집합으로 다 기억해서 결정적으로 전이하게 바꾼 거야♡

수락 상태는 q₄가 포함된 모든 집합! (D, E, F)

NFA는 가능성의 기계, DFA는 확정의 기계야.
NFA → DFA는 그 가능성들을 상태의 집합으로 묶어 확정시키는 과정이지♡

1. DFA

2. NFA

3. NFA->DFA 변환

티스토리툴바