FSM   Finite State Machine   유한상태 기계, 유한상태 머신

(2024-02-18)

스테이트 머신, 상태 머신, 유한상태기, Finite Automata, 유한 오토마타, Automation, 오토마타


1. 오토마타 (Automaton, Automata)

  ㅇ 자동 기계(自動機械, 스스로 움직이는 기계)에 대한 추상적 모형
     - 주로, 언어에 밀접하게 관련지을 때 쓰이는 말

  ㅇ 영어 표현으로, 
     - 단수형은, 오토마튼/오토머튼 (automaton)
     - 복수형은, 오토마타/오토머터 (automata)

  ㅇ 구분
     - 유한 오토마타
     - 푸시다운 오토마타


2. 유한 상태 기계 (Finite State Machine, FSM) 또는 유한 오토마타 (Finite Automata)

  ㅇ 유한 상태를 갖으며, 입력 및 현재 상태에 따라, 상태가 천이(전환)되는 기계에 대한 추상적 모형
     - 즉, 디지털 시스템,디지털 컴퓨터 등에 대한 추상적 모델로 볼 수 있음

  ㅇ 유한 상태 집합 내에서 움직임
     - 시간 진행에 따라, 미리 정해진 유한 상태들의 집합 내에서, 그 상태가 변할 수 있는 장치
        . 이산 시간 마다 주어진 입력에 의존하여 작동하는 수학적인 기계

  ㅇ 기본적으로, 내부에 유한한 메모리(기억성)가 있는 자동 기계에 대한 추상적모형
     - 유한한 기억장치(유한한 개수의 상태)를 갖는 자동 기계에 대한 추상적 모형
     - 과거의 상태/신호들을 저장하는 메모리 용량이 유한개인 장치를 가리키는 일반적인 용어


3. 유한 상태 기계의 요소 및 특징

  ㅇ 유한상태기계 주요 개념적 요소들
     - 상태(State)   : 특정 시간에 처한 상황
     - 상태 간 천이(전이) : 상황 변화
     - 이벤트(Event) : 상태 간 전이를 유발시키는 사건 즉, 입력
     - 행동(동작)    : 이벤트에 반응하여 다른 상태로 전이할 때 하는 일/동작/행동

     * 즉,
        . 유한한 상태의 집합을 갖고, 
        . 한번에 하나의 상태 만을 갖으며,
        . 입력(이벤트) 발생하면,
        . 정해진 다음 상태로 천이하며,
        . 출력을 내놓음
           .. 입력의 끝을 만나거나 특정 상태에 이르면 정지하며, 이때 문자열을 수용 또는 거부 함

  ㅇ 특징
     - 정확하고 엄격한 매칭 조건 만 가능 (즉, 근사 매칭은 허용 안함)


4. 유한 상태 기계의 유형예측 가능 여부에 따라
     - 결정론적 유한 상태 기계
        . 입력에 대해 하나의 상태 전환(천이) 만 허용 (예측 가능)
     - 비결정론적 유한 상태 기계
        . 입력에 대해 1 이상의 상태 전환(천이)이 가능 (예측 불가능)

  ㅇ 현재 상태,입력 의존성에 따라
     - 무어 머신 (Moore Machine) : 출력이 현재 상태에 의해서 만 결정됨
        . 즉, 플립플롭 출력들(현재 상태들)의 조합에 의해서 만 결정됨
     - 밀리 머신 (Mealy Machine) : 출력이 현재 상태와 입력 모두에 의해서 결정됨
        . 즉, 같은 상태라도 입력에 따라서 달라질 수 있음


5. 유한 상태 기계의 용도

  ㅇ 상태를 갖는 동작을 표현/이해/설명하고, 설계하기 위한, 
     체계적이고 수학적인 방법의 틀을 제공

  ㅇ 例)
     - 순서논리회로
     - 컴퓨터
     - 프로토콜
     - 컴파일러
     - 형식언어
     - 알고리즘 설계6. 유한 상태 기계의 표현

  ㅇ 유한상태기계의 도표/도형적 표현은,  ☞ 상태표/상태도 참조

  ㅇ 유한상태기계의 그래프 표현은, 특수한 방향 그래프로 가능
     - 단일 출발 상태, 단일 도착 상태, 다수 중간 상태로 구성
     - 각 선분은 다음 상태로 들어가는 조건을 갖음

순서회로 묘사
   1. 상태   2. 상태표,상태도   3. 타이밍도   4. 기억성   5. 유한상태 기계  
컴파일러
   1. 컴파일   2. 전처리   3. 어휘 분석, 구문 분석, 의미 분석   4. 링커 및 로더   5. 형식 언어   6. 유한상태 머신   7. BNF,EBNF  


"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"