Finite State Machine

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)
오토마타 (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 :
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.
[출처]http://www.aistudy.com/math/finite_state_machine.htm