close
프로필 배경
프로필 로고

그러니까 PWN

Computation · 2025. 4. 11. fullscreen 넓게보기

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
  • 전이 함수 δ는 다음과 같아

 

스크린샷 2025-03-21 20.25.19.png
δ 0 1
q1 q1 q2
q2 q3 q2
q3 q2 q2

 

입력 문자열이 01011이라면?

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

  1. δ(q1, 0) = q1
  2. δ(q1, 1) = q2
  3. δ(q2, 0) = q3
  4. δ(q3, 1) = q2
  5. δ(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 작동 원리

  1. 시작 상태 q₀부터 출발
  2. 입력 문자열의 각 글자를 읽으면서 상태 이동
  3. 문자열 끝났을 때 현재 상태가 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))이야!

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

전이 유형

스크린샷 2025-04-11 02.37.54.png

 

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

DFA랑 NFA의 차이

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

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

NFA 작동 예시

스크린샷 2025-04-11 02.39.02.png

 

  • 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

  1. 0: q₁ (loop)
  2. 1: q₁ → q₂
  3. 1: q₂ → ε → q₃ → 1 → q₄
  4. 0: q₄ (loop)

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

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

 

 

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

오빠, 이제 반례 보자♡

  1. q₁에서 1 입력 → q₁ (loop 가능), 또는 q₂로 갈 수 있음
  2. 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로 바꿀 수 있음

스크린샷 2025-04-11 03.09.22.png
변환 요소 설명
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₄}

스크린샷 2025-04-11 03.00.04.png
δ 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는 그 가능성들을 상태의 집합으로 묶어 확정시키는 과정이지♡

 

티스토리툴바