State machine 문서 원본 보기

[[분류: 프로그래밍 언어]]

== 개요 ==

'''상태 기계(State Machine)'''는 프로그램이나 시스템이 가질 수 있는 다양한 상태와 상태 간의 전이(transition)를 모델링한 수학적 개념이다. 이는 특정 입력이나 조건에 따라 상태가 어떻게 변화하는지를 설명하며, 소프트웨어 개발, 제어 시스템 설계, 하드웨어 설계 등 다양한 분야에서 사용된다.

== 구성 요소 ==
상태 기계는 다음의 기본 구성 요소로 이루어진다:
* '''상태 (State)''': 시스템이 특정 시점에 놓일 수 있는 상태.  
  예: 신호등 시스템의 상태는 "빨간불", "노란불", "초록불"과 같은 상태로 정의될 수 있다.
* '''입력 (Input)''': 상태를 변화시키는 외부 요인.  
  예: 버튼 입력, 시간 경과, 사용자 명령 등.
* '''전이 (Transition)''': 하나의 상태에서 다른 상태로 변화하는 규칙 또는 조건.  
  예: 초록불 상태에서 일정 시간이 지나면 노란불 상태로 전환.
* '''초기 상태 (Initial State)''': 시스템이 시작될 때의 상태.
* '''종료 상태 (Final State)''': 시스템이 종료되었음을 나타내는 상태(필요한 경우).

== 유형 ==
상태 기계는 사용 목적과 동작 방식에 따라 다양한 유형으로 나뉜다:
* '''유한 상태 기계 (Finite State Machine, FSM)''': 상태의 개수가 유한한 상태 기계. 가장 일반적으로 사용되며, 다시 두 가지로 나뉜다:
** '''디터미니스틱 유한 상태 기계 (Deterministic FSM)''': 동일한 입력이 항상 동일한 전이를 일으키는 상태 기계.
** '''비디터미니스틱 유한 상태 기계 (Non-Deterministic FSM)''': 동일한 입력이 여러 전이 중 하나를 선택할 수 있는 상태 기계.

* '''푸쉬다운 오토마타 (Pushdown Automaton)''': 추가적으로 스택을 사용하여 입력과 상태를 관리하는 상태 기계. 주로 언어 및 구문 분석에서 사용된다.

* '''튜링 기계 (Turing Machine)''': 상태 기계의 일반화된 형태로, 임의의 계산 가능한 문제를 처리할 수 있다.

== 장점 ==
* '''명확한 모델링''': 시스템의 상태와 동작을 명확하게 표현할 수 있다.
* '''효율적인 설계''': 복잡한 시스템을 상태 기반으로 분리하여 설계할 수 있다.
* '''디버깅 용이성''': 상태와 전이를 기반으로 오류를 쉽게 추적할 수 있다.

== 단점 ==
* 상태의 개수가 많아질수록 관리가 어려워지는 상태 폭발(state explosion) 문제가 발생할 수 있다.
* 복잡한 시스템에서 상태 전이 규칙을 정의하는 데 많은 시간이 소요될 수 있다.
* 상태 간의 의존성이 높아질 경우 설계가 비효율적일 수 있다.

== 시각화 방법 ==
상태 기계는 일반적으로 상태 다이어그램으로 시각화된다.  
* 각 상태는 '''원(circle)'''으로 표현된다.
* 상태 간의 전이는 '''화살표(arrow)'''로 연결된다.
* 초기 상태는 '''화살표가 들어오는 단일 원'''으로 나타낸다.
* 종료 상태는 '''이중 원(double circle)'''으로 나타낸다.