Finite  State  Machine

 

계산이론 (Theory of Computation) 에서 finite state machine (FSM) 또는 finite state automaton (FSA) 은 단지 유한한 일정한 양의 메모리 (memory) 만을 가지는 추상 기계이다. 그 기계의 내부 상태 (state) 는 더 이상의 구조를 갖지 않는다. 이러한 종류의 모델은 계산과 언어 (computation and languages) 의 연구에 아주 광범위하게 사용된다. .... (Wikipedia : Finite state machine)

상태라는 개념부터 들어가 보자. 선풍기 같은 단순한 기계를 생각해 보자. 선풍기를 제어하는 수단이 켜고 끄는 스위치뿐이라고 가정하자. 그때 우리는 선풍기가 가능한 상태 두 가지 중의 하나에 놓여 있다고 말할 수 있다. 이제 3단계 속도를 가진 또 하나의 선풍기를 생각해 보자. 그것은 가능한 상태 네 가지 중 하나에 있을 것이다(끔, 느린 속도, 중간 속도, 빠른 속도). 이제는 속도를 연속으로 조정할 수 있는 고급 모델 선풍기를 생각해 보자. 이 경우 속도의 연속적인 폭 때문에 모든 가능한 상태를 항목화할 수 없다. 1과 2 사이의 모든 분수를 적으려는 것과 같다.

다음, 유한의 개념을 생각해 보자. 유한은 한계를 지웠다는 의미이다. 따라서 앞의 두 선풍기는 한계를 지운, 또는 유한 개수의 가능한 상태 2 와 4 를 각각 가진 것이라고 말할 수 있다.

.... 유한 개수 상태를 가진 기계인 두 선풍기가 유한 상태 기계라고 생각할 수 있을 것이다. 그러나 FSM 은 유한 개수 상태를 가진 기계라는 것 이상의 의미를 가지고 있다 ..... 특히 하나의 FSM 은

컴퓨터는 FSM의 완벽한 보기이다 ..... 컴퓨터가 FSM 의 좋은 예라고 하는 것이 그리 새삼스러운 것은 아니다. Alan Turing 은 작동할 때 규칙들을 읽어들일 수 있는 FSM 이 보편적인 컴퓨터임을 이미 1936년에 증명해 보였다. ......... (Stephen Prata 1994)

Term :

유한상태 기계 (Finite State Machine)     오토마타 (Automata)   오토마타 이론 (Automata Theory)    세포 자동자 (Cellular Automata)    튜링 기계 (Turing Machine)

Paper :

유한상태기계 (Finite State Machine : FSM) : Stephen Prata

방향코드와 유한 오토마타를 이용한 사람 동작 프리미티브 패턴 분류기의 구현 (Implementation of a Primitive Pattern Classifier for Human Body Motion Using Direction Code and Finite Automata) : 조형제, 조경은, 한국멀티미디어학회, 1999

상태 오토마타와 기본 요소분류기를 이용한 가상현실용 실시간 인터페이싱 (Virtual Environment Interfacing based on State Automata and Elementary Classifiers) : 민병의, 박치항, 김종성, 이찬수, 송경준, 한국정보처리학회, 1997

유한 상태 오토마타의 추론을 위한 이차 순환 신경망의 학습 시간 단축 (Reducing learning time of Second-order Recurrent Neural Network inferring Finite State Automata) : 류수길, 강효진, 정현기, 정순호, 한국멀티미디어학회, 1999

Site :

Wikipedia : Finite state machine

The Finite State Machine Explorer :  An interactive Java applet which simulates a finite state machine. Source code available. state machine 의 정의  The Finite State Machine Simulatore Another Java state machine simulator with source code.    

Video :

Finite-State Machines - Basics : Explanation & Example : 2014/09/15

 

Finite State Machines : MIT : Chris Terman, 2013/02/26

 

Introduction to Finite-State Machines and Regular Languages : UCDavis : 2012/12/11