사용자:Chugun/Editing9

S · L · J · P · G · B · I · T · M · E | 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 · 10 · 11 · 12 · 전체 하위 문서
Mediawiki 1.43.0-wmf.2 (ce9d259) :: 666,695 articles / 3,212,877 pages / 838,693 users / 36,748,653 edits / 13,793 files
Page cached 2024-04-27T12:18:34+00:00 / Revision - / 3,079 bytes

유한 오토마타, 유한 오토마톤(←영어: Finite-state Automaton; FA), 또는 유한 상태 기계(영어: Finite-state machine, FSM)는 디지털 논리 회로나 컴퓨터 프로그램을 설계하는데 있어 중요한 추상 기계 중의 하나로, 유한한 수의 상태를 가진 일종의 컴퓨터 모델이다. 한 기계는 하나의 상태만을 동시에 가질 수 있으며, 최초 상태에서 입력 기호를 하나씩 읽으면서 상태를 변화해간다. 정의된 최종 상태에 이르는 순간 성공, 또는 그 기호열을 수용했다 한다.

유한 오토마타는 여러 가지 문제에 적용이 가능하며, 그 중에서도 주로 반도체 설계의 자동화나, 통신 규약의 설계, 또는 구문 구조의 분석 등 여러가지 공학적 요소에 사용되고 있다. 생물학이나 인공 지능 연구 등에서는 이를 여러 개로 묶어 신경계를 모델화하기도 하며, 언어학에서는 자연 언어의 문법을 모델화하는데 사용하기도 한다.

개념과 용어

유한 오토마타에서 상태(state)는 기계가 어떠한 동작을 수행하면서 읽은 정보에 따라 변하는 것으로, 읽은 기호에 따라서 상태가 변화할 수 있다. 일반적으로 새로운 상태는 시스템이 같은 기호를 읽었지만 다른 동작을 할 필요가 있을때 만들어지거나 한다. 예컨대, 승강기가 현재 4층에 있고, 3층 버튼을 누른다면 밑으로 내려가야 하지만, 2층에 있었다면 위로 올라가야 한다. 이럴 때에 "2층에 있었다"는 것과 "4층에 있었다"는 것은 서로 다른 상태를 나타낸다. 전환(transition)은 기호를 읽어 상태가 변화하는 것을 나타낸다.

동작(action)은 그 시점에서 유한 오토마타가 실행해야 하는 것을 나타내며, 유한 오토마타가 할 수 있는 동작에는 다음과 같은 것들이 있다:

• 시작(Entry): 해당 상태에 들어가면서 하는 동작
• 종료(Exit): 해당 상태에서 나오면서 하는 동작
• 입력(Input): 해당 상태와 입력 조건에 따르는 동작
• 전환(Transition): 이동시에 실행되는 동작

표현법

유한 오토마타를 나타내는 방법에는 여러 가지가 있으며, 그 중 한 방법으로는 다음 표와 같이 상태 전환 표(State transition table)를 이용해 나타내는 방법이 있다. 가로축에는 현재 상태가, 세로축에는 새 입력이 나오며 해당 입력을 받았을 때 바뀌게 된 뒤의 상태를 두 값이 교차하는 곳에 기록한다.

[표 1] 상태 전환 표의 예시

	상태 A	상태 B	상태 C
입력 X	...	...	...
입력 Y	...	상태 C	...
입력 Z	...	...	...