FSM과 DFA, NFA의 개념과 차이

graph TD
  %% 노드 정의
  FSM["🧠 FSM<br/>(Finite State Machine)"]
  DFA["🔵 DFA<br/>(Deterministic Finite Automaton)"]
  NFA["🟢 NFA<br/>(Non-deterministic Finite Automaton)"]
  Mealy["🟡 Mealy Machine"]
  Moore["🟠 Moore Machine"]

  DFA_Desc["📘 설명:<br/>결정적, 예측 가능"]
  NFA_Desc["📗 설명:<br/>비결정성, ε-전이 가능"]
  Mealy_Desc["📒 출력:<br/>전이와 함께 발생"]
  Moore_Desc["📙 출력:<br/>상태 기반 발생"]

  %% 관계 연결
  FSM --> DFA
  FSM --> NFA
  FSM --> Mealy
  FSM --> Moore

  DFA -->|입력마다<br/>정확히 1개의 전이| DFA_Desc
  NFA -->|동일 입력에<br/>여러 전이 가능| NFA_Desc
  Mealy -->|입력-출력<br/>기반 동작| Mealy_Desc
  Moore -->|출력은<br/>상태에 따라| Moore_Desc

  %% 스타일 정의
  classDef fsmStyle fill:#dde6f1,stroke:#4a78b6,stroke-width:2px,color:#000,font-weight:bold;
  classDef dfaStyle fill:#cce5ff,stroke:#004085,color:#002752;
  classDef nfaStyle fill:#d4edda,stroke:#155724,color:#0b2e13;
  classDef mealyStyle fill:#fff3cd,stroke:#856404,color:#533f03;
  classDef mooreStyle fill:#ffe5b4,stroke:#8a6d3b,color:#4b3832;
  classDef descStyle fill:#f8f9fa,stroke:#6c757d,color:#343a40,font-size:0.9em;

  class FSM fsmStyle;
  class DFA dfaStyle;
  class NFA nfaStyle;
  class Mealy mealyStyle;
  class Moore mooreStyle;

  class DFA_Desc,NFA_Desc,Mealy_Desc,Moore_Desc descStyle;

💡 FSM (Finite State Machine)

FSM(유한 상태 기계)는 유한한 수의 상태(State)와 입력(Input)을 기반으로 동작하는 추상적인 계산 모델입니다. 어떤 상태에서 특정 입력이 들어오면, 정해진 규칙에 따라 다음 상태로 전이(Transition)됩니다.

• 상태(State): 시스템이 가질 수 있는 내부 상태
• 입력(Input): 외부로부터 들어오는 자극 또는 이벤트
• 전이(Transition): 입력에 따른 상태 변화
• 초기 상태(Start State), 종료/수락 상태(Accept State)

✅ DFA (Deterministic Finite Automaton)

DFA(결정적 유한 오토마톤)는 FSM의 특수한 형태로, 모든 상태에서 각 입력에 대해 단 하나의 전이만 허용됩니다.

• 모든 상태에서 모든 입력에 대해 반드시 하나의 전이만 존재
• 비결정성(Nondeterminism)이 없음
• 전이 경로가 항상 명확하며 예측 가능함

🧱 FSM (NFA vs DFA) 비교

항목	FSM	DFA
정의	입력에 따라 상태가 전이되는 기계	각 입력에 대해 정확히 하나의 전이
전이 수	0개 이상 가능 (비결정성 허용)	각 입력에 대해 오직 1개
비결정성	허용	불허
활용 예시	게임 로직, 프로토콜 모델링 등	문자열 패턴 탐색, 구문 분석 등

---

🎟️ DFA 예시 1: 지하철 개찰구 시스템

지하철의 개찰구 시스템은 입력(승객 접근, 교통카드 인식 등)에 따라 상태가 전이되는 대표적인 FSM 구조입니다. 이 예시는 현실에서 FSM이 어떻게 동작하는지 직관적으로 보여줍니다.

• IDLE: 아무도 없는 초기 상태
• CARD_WAIT: 승객이 접근했지만 아직 카드를 대지 않음
• OPEN: 유효한 카드가 인식되어 문이 열림
• ERROR: 카드 오류 또는 무효 입력 발생

전이 규칙:

• IDLE → CARD_WAIT : 승객 접근
• CARD_WAIT → OPEN : 유효한 카드
• CARD_WAIT → ERROR : 무효 카드
• OPEN → IDLE : 승객 통과
• ERROR → IDLE : 관리자 초기화 또는 승객 후퇴

stateDiagram
  [*] --> IDLE
  IDLE --> CARD_WAIT : 승객 접근
  CARD_WAIT --> OPEN : 유효한 카드
  CARD_WAIT --> ERROR : 무효 카드
  OPEN --> IDLE : 승객 통과
  ERROR --> IDLE : 초기화 또는 후퇴

🤯 NFA 예시 3: 감정 기복형 인간의 하루 루틴

기분파/감정기복형 인간을 기반으로, 하루 동안 겪는 감정 상태 변화 과정을 FSM으로 설계합니다.

🧩 상태 정의

상태	설명
침대 속(VOID)	무기력, 아무 것도 하기 싫음
출근 준비(WAKING)	억지로 기상 후 정신 차리는 중
회의 스트레스(STRESS)	줌 회의, 피드백 폭격, 정신 공황
카페인 폭주(BURST)	커피빨로 각성. 갑자기 텐션↑
집중의 신(ZEN)	몰입 시작. 마감 시간 전 몰아치는 집중력
뇌 OFF(SHUTDOWN)	퇴근 후 모든 기능 정지
리셋(RECOVERY)	다음 날을 위한 자가 회복 단계

🔁 전이 규칙

현재 상태	입력 이벤트	다음 상태
침대 속	알람 울림	출근 준비
출근 준비	회의 시작	회의 스트레스
회의 스트레스	커피 투입	카페인 폭주
카페인 폭주	집중 시작	집중의 신
집중의 신	퇴근 시간	뇌 OFF
뇌 OFF	야식 or 명상	리셋
리셋	아침 도착	침대 속
회의 스트레스	슬랙 폭탄	침대 속 (포기함)

🤹 특별 요소: 되돌아감(Loop) 및 조기 종료

• 회의 스트레스 상태에서 슬랙 알림 + 피드백 폭탄을 받으면 바로 포기하고 침대로 도망감.
• 뇌 OFF 상태에서 야식을 먹으면 회복으로 전이되지만, 과식을 하면 다시 VOID로 되돌아갈 수 있음 (응급 전이 가능성).

stateDiagram
  [*] --> 침대_속
  침대_속 --> 출근_준비 : 알람
  출근_준비 --> 회의_스트레스 : 회의 시작
  회의_스트레스 --> 카페인_폭주 : 커피
  회의_스트레스 --> 침대_속 : 슬랙 폭탄
  카페인_폭주 --> 집중의_신 : 몰입 시작
  집중의_신 --> 뇌_OFF : 퇴근
  뇌_OFF --> 리셋 : 야식 or 명상
  리셋 --> 침대_속 : 아침 도착

---

 

🧪 NFA 예시 1: 문자열에 "ab" 또는 "ba" 포함 여부 판별기

다음은 입력 문자열에 "ab" 또는 "ba"가 포함되었는지를 판별하는 NFA입니다. 이 경우, 동일한 상태에서 동일한 입력으로 여러 경로로 전이할 수 있으므로 DFA로는 복잡해지지만, NFA에서는 간단하게 표현됩니다.

stateDiagram
  [*] --> S0
  S0 --> S0 : a
  S0 --> S0 : b
  S0 --> S1 : a
  S0 --> S3 : b
  S1 --> S2 : b
  S3 --> S4 : a
  S2 --> [*] : ab 포함
  S4 --> [*] : ba 포함

설명: S2 또는 S4에 도달하면 문자열에 "ab" 또는 "ba"가 포함되었음을 의미하며, 이 두 상태가 수락 상태입니다.

🤣 NFA 예시 2: 피자 주문 고민 오토마톤

(부제: "마음은 이미 피자")

이 예시는 인간의 흔들리는 마음을 표현한 유머러스한 NFA입니다. 동일한 상황에서 여러 감정적 전이 경로가 존재하므로 NFA로 모델링에 적합합니다.

상태	설명
START	저녁 시간, 배고픔 감지
SEARCH	배달 앱 탐색
CRAVING	피자 먹고 싶음 폭발
RESIST	살찔까봐 고민 중
ORDER	피자 주문 완료 (Accept ✅)

stateDiagram
  [*] --> START
  START --> SEARCH : 배고픔
  SEARCH --> CRAVING : 피자 발견
  SEARCH --> RESIST : 가격 확인
  CRAVING --> ORDER : 버튼 클릭
  RESIST --> CRAVING : 피자 사진 또 봄
  RESIST --> ORDER : 의지 약화됨
  CRAVING --> RESIST : 다이어트 각성
  ORDER --> [*] : 수락 상태 (피자 도착)

해설: RESIST 상태에서 ORDER 또는 다시 CRAVING으로 갈 수 있는 비결정적 전이 구조가 NFA의 특징을 잘 보여줍니다. 인간의 마음도 결국 NFA입니다.

---

📏 DFA 예시 1: "ab"로 끝나는 문자열 판별기

입력 문자열이 "ab"로 끝나는지를 판별하는 DFA의 상태 전이 구조입니다. S2는 수락 상태 (Accept State)입니다.

stateDiagram
  [*] --> S0
  S0 --> S1 : a
  S0 --> S0 : b
  S1 --> S1 : a
  S1 --> S2 : b
  S2 --> S1 : a
  S2 --> S0 : b
  S2 --> [*] : 입력 종료시 accept

🎓 DFA 예시 2: 과제 제출 여부 판별 오토마톤

(부제: “그 학생은 정말 과제를 제출했을까?”)

💡 콘셉트

• 입력 문자열은 학생의 과제 관련 행동 흐름을 표현합니다.
• 각 문자(입력)는 특정 행동을 의미하고, DFA는 이 행동들의 순서를 분석하여 실제로 과제를 제출했는지 판단합니다.

🧾 입력 기호 정의

입력 문자	의미
w	과제를 하려고 워드 열기
t	딴짓 시작 (웹툰, 유튜브, 카톡 등)
d	과제 일부 작성
s	제출 버튼 클릭
n	제출 안 하고 그냥 꺼버림

🧩 상태 정의

상태	설명
S0	초기 상태 (과제 전)
S1	워드 열고 멀쩡한 상태
S2	잠깐 딴짓함
S3	과제를 실제로 작성함
S4	제출 완료 (Accepting State ✅)
F	제출 실패 (끝, 못 돌아감 😭)

🔁 전이 규칙 (DFA)

현재 상태	입력	다음 상태	설명
S0	w	S1	워드 파일 열기
S1	t	S2	딴짓함
S1	d	S3	과제 쓰기 시작
S2	d	S3	마음 다잡고 작성 재개
S2	t	S2	또 딴짓 중
S3	d	S3	계속 작성
S3	s	S4	제출 완료 ✅
S3	n	F	그냥 꺼버림 ❌
S0~S3	n	F	어떤 상태에서든 강제 종료 시 실패

stateDiagram
  [*] --> S0
  S0 --> S1 : w
  S1 --> S2 : t
  S1 --> S3 : d
  S2 --> S2 : t
  S2 --> S3 : d
  S3 --> S3 : d
  S3 --> S4 : s
  S4 --> [*] : 제출 성공 후 종료 ✅
  S0 --> F : n
  S1 --> F : n
  S2 --> F : n
  S3 --> F : n

🧠 마무리 요약

• FSM은 상태 기반 로직의 기반 개념으로, 다양한 시스템에 적용됩니다.
• DFA는 FSM의 결정적 버전으로, 입력에 대한 전이가 항상 하나로 고정되어 있어 효율적인 처리가 가능합니다.
• 실생활에서도 FSM은 자동문, 인증 시스템, 교통 제어 등 다양한 곳에서 사용됩니다.
  

  

  
  

  

  원본 이미지 출처: https://www.abstractsyntaxseed.com/blog/regex-engine/implementing-a-nfa