1. 오토마타 (Automaton, Automata)
ㅇ 자동 기계(自動機械, 스스로 움직이는 기계)에 대한 추상적 모형
- 주로, 언어에 밀접하게 관련지을 때 쓰이는 말
ㅇ 영어 표현으로,
- 단수형은, 오토마튼/오토머튼 (automaton)
- 복수형은, 오토마타/오토머터 (automata)
ㅇ 구분
- 유한 오토마타
- 푸시다운 오토마타
2. 유한 상태 기계 (Finite State Machine, FSM) 또는 유한 오토마타 (Finite Automata)
ㅇ 유한 상태를 갖으며, 입력 및 현재 상태에 따라, 상태가 천이(전환)되는 기계에 대한 추상적 모형
- 즉, 디지털 시스템,디지털 컴퓨터 등에 대한 추상적 모델로 볼 수 있음
ㅇ 유한 상태 집합 내에서 움직임
- 시간 진행에 따라, 미리 정해진 유한 상태들의 집합 내에서, 그 상태가 변할 수 있는 장치
. 이산 시간 마다 주어진 입력에 의존하여 작동하는 수학적인 기계
ㅇ 기본적으로, 내부에 유한한 메모리(기억성)가 있는 자동 기계에 대한 추상적인 모형
- 유한한 기억장치(유한한 개수의 상태)를 갖는 자동 기계에 대한 추상적 모형
- 과거의 상태/신호들을 저장하는 메모리 용량이 유한개인 장치를 가리키는 일반적인 용어
3. 유한 상태 기계의 요소 및 특징
ㅇ 유한상태기계 주요 개념적 요소들
- 상태(State) : 특정 시간에 처한 상황
- 상태 간 천이(전이) : 상황 변화
- 이벤트(Event) : 상태 간 전이를 유발시키는 사건 즉, 입력
- 행동(동작) : 이벤트에 반응하여 다른 상태로 전이할 때 하는 일/동작/행동
* 즉,
. 유한한 상태의 집합을 갖고,
. 한번에 하나의 상태 만을 갖으며,
. 입력(이벤트) 발생하면,
. 정해진 다음 상태로 천이하며,
. 출력을 내놓음
.. 입력의 끝을 만나거나 특정 상태에 이르면 정지하며, 이때 문자열을 수용 또는 거부 함
ㅇ 특징
- 정확하고 엄격한 매칭 조건 만 가능 (즉, 근사 매칭은 허용 안함)
4. 유한 상태 기계의 유형
ㅇ 예측 가능 여부에 따라
- 결정론적 유한 상태 기계
. 입력에 대해 하나의 상태 전환(천이) 만 허용 (예측 가능)
- 비결정론적 유한 상태 기계
. 입력에 대해 1 이상의 상태 전환(천이)이 가능 (예측 불가능)
ㅇ 현재 상태,입력 의존성에 따라
- 무어 머신 (Moore Machine) : 출력이 현재 상태에 의해서 만 결정됨
. 즉, 플립플롭 출력들(현재 상태들)의 조합에 의해서 만 결정됨
- 밀리 머신 (Mealy Machine) : 출력이 현재 상태와 입력 모두에 의해서 결정됨
. 즉, 같은 상태라도 입력에 따라서 달라질 수 있음
5. 유한 상태 기계의 용도
ㅇ 상태를 갖는 동작을 표현/이해/설명하고, 설계하기 위한,
체계적이고 수학적인 방법의 틀을 제공
ㅇ 例)
- 순서논리회로
- 컴퓨터
- 프로토콜
- 컴파일러
- 형식언어
- 정규표현식 계산 모델
- 알고리즘 설계 등
6. 유한 상태 기계의 표현
ㅇ 유한상태기계의 도표/도형적 표현은, ☞ 상태표/상태도 참조
ㅇ 유한상태기계의 그래프 표현은, 특수한 방향 그래프로 가능
- 단일 출발 상태, 단일 도착 상태, 다수 중간 상태로 구성
- 각 선분은 다음 상태로 들어가는 조건을 갖음