유한 상태 기계

유한 상태 기계(finite-state machine, FSM) 또는 유한 오토마톤(finite automaton, FA; 복수형: 유한 오토마타 finite automata)는 컴퓨터 프로그램과 전자 논리 회로를 설계하는 데에 쓰이는 수학적 모델이다. 간단히 '상태 기계'라고 부르기도 한다. 
유한 상태 기계는 유한한 개수의 상태를 가질 수 있는 오토마타, 즉 추상 기계라고 할 수 있다. 이러한 기계는 한 번에 오로지 하나의 상태만을 가지게 되며, 현재 상태(Current State)란 임의의 주어진 시간의 상태를 칭한다. 이러한 기계는 어떠한 사건(Event)에 의해 한 상태에서 다른 상태로 변화할 수 있으며, 이를 전이(Transition)이라 한다. 특정한 유한 오토마톤은 현재 상태로부터 가능한 전이 상태와, 이러한 전이를 유발하는 조건들의 집합으로서 정의된다.

수리 기계와 인식기

수리 기계(acceptors)와 인식기(recognizers)는 입력값이 기계에서 받아 들여졌는지 이진값인 '예 또는 아니오'로 결과를 출력한다. 유한 오토마타의 모든 상태는 받아들여지는지 또는 받아들여지지 않는지에 대한 값을 가지고 있다. 모든 입력이 처리되었을때, 만약 현재 상태가 받아들여질 수 있는 상태라면 그 입력값은 기계에 의해 받아들여진 것이다. 반대로 현재 상태가 받아들여질 수 없는 상태라면 그 입력값은 거부된 것이다.
유한 오토마타는 언어를 정의하는 데에도 사용될 수 있다. 받아들여지는 모든 단어를 포함하고 그 문법으로 기계를 구성할 수도 있다. 이렇게 유한 오토마타로 구성이 가능한 언어를 "유한 오토마타가 받아들일 수 있는 언어"라고 한다. 정의에 의해 유한 오토마타가 받아들일 수 있는 모든 언어는 정규 표현식이다. 또한 역도 성립한다. 즉, 모든 정규 표현식은 유한 오토마타가 받아들일 수 있다.

결정론

유한 오토마타는 결정적 유한 오토마타(Deterministic Finite Automata, DFA) 와 비결정적 유한 오토마타(Non-Deterministic Finite Automata, NFA) 오토마타로 나눌 수 있다.
결정적 유한 오토마타에서 모든 상태는 각각의 가능한 입력에 대해 정확히 하나의 변환된 상태를 가질 수 있다. 비 결정적 유한 오토마타에서 입력은 주어진 상태에 대해 한 가지 또는 여러 가지의 변환된 상태를 가지게 할 수 있다. 여러 알고리즘(the powerset construction 등)을 사용하여 어떠한 NFA라도 동일한 기능을 가지는 DFA로 변환할 수 있다.

비결정적 유한 오토마타의 결정적 유한 오토마타로의 변환

멱집합 구성(Powerset Construction) 혹은 부분집합 구성방식은 유한 오토마타 변환의 표준이라고 할 수 있는 방법이다. 이 방식에서, 같은 정규 언어를 인식하는 비결정적 유한 오토마타는 결정적 유한 오토마타로 변환된다. 이 이론에서 중요한 점은, 비결정적 유한 오토마타가 더 유연함에도 불구하고 그것들은 결정적 유한 오토마타가 인지하지 못하는 어떠한 언어도 인지할 수 없다는 점이다. 또, 비결정적 유한 오토마타를 결정적 유한 오토마타로 변환하는 가장 큰 이유는, 더 쉽게 구성되는 비결정적 유한 오토마타를 컴퓨터에서 효율적으로 실행할 수 있는 결정적 유한 오토마타로 바꾸기 위함이다. 하지만, 만일 비결정적 유한 오토마타가 n개의 상태를 가지고 있다면, 얻어지는 결정적 유한 오토마타는 최대 2ⁿ 개의 상태를 가지고 있으며, 이는 지수적으로 증가하므로 종종 큰 비결정적 유한 오토마타에 대해 이 변환은 비실용적이다.

예시

밑의 NFA는 네가지 상태를 가진다. 1은 최초 상태이고, 3과 4는 받아들여지는 상태이다. 각각의 알파벳은 0과 1의 두 기호로 구성되어있으며, 각각은 ε-move를 가진다.
이 비결정적 오토마타로부터 얻어지는 결정적 오토마타의 최초 상태는 모든 비결정적 오토마타가 1로부터 ε-move를 통해 도달 가능한 상태이다. 즉, 이 경우에는 {1,2,3}이 된다.
{1,2,3}으로부터 입력 기호 0에 의한 전이는 상태 1 에서 상태 2로 가는 화살표를 따라가거나, 상태 3으로부터 상태 4로의 방향을 따라야 한다. 덧붙여서, 상태 2와 상태 4는 밖으로 나가는 ε-move 를 가지지 않는다. 그러므로, T({1,2,3},0) = {2,4} 가 되고, 같은 방식으로 비결정적 유한 오토마타로부터 생성된 결정적 유한 오토마타는 밑의 그림과 같다.
이 예시에서, 결정적 유한 오토마타는 시작 상태로부터 5개의 도달 가능한 상태를 가진다. 나머지 11개의 부분 집합은 도달 불가능하다.

고대와 중세(~16세기)

유한 오토마타는 디지털 컴퓨터에 대한 추상적 모델로서, 19세기 중반 다양한 분야의 과학자들이 협력하여 인간의 사고 과정을 컴퓨터 또는 다른 이론적 모델을 통해 표현해 내고자 하는 데서 연구의 기원을 찾을 수 있다.
유한 오토마타의 개념이 나오기 이전 시대의 경우, 유한 오토마타와 유사성 또는 관련성이 있는 오토마타(Automata), 즉 자동기계의 개념이 존재하였다. 이는 인간에 의한 복잡한 제어 없이 스스로 제 기능을 하는 기계들(self-operating machine)를 의미한다. 인류는 오래전부터 이러한 자동기계에 흥미를 느끼고 만들고 개발시켜 왔다.
오토마타, 즉 자동기계는 헬레니즘 시대와 고대 그리스 시대부터 이미 존재했다고 알려져 있다. 헬레니즘 시대(Hellenistic World)의 오토마타는 장난감, 종교적 신상(idol), 또는 기본적 과학 원리들을 증명하는 도구 등으로 만들어졌다.
고대 그리스 수학자인 알렉산드리아의 헤론은 수력으로 작동하는 오르간, 소화기, 사이펀과 같은 기계들에 대한 기록을 남겼으며, 이것들은 최초의 오토마타라고 여겨진다. 뿐만 아니라 아르키메데스는 스스로 작동하는 천체 모형을 만들었다고 전해진다.
오토마타의 형성과 발전은 물시계와 연관이 깊은데, 기원전 250년경에 고대 그리스 과학자 크테시비우스는 기계장치 자동인형이 부착된 최초의 자동물시계 '클렙시드라'를 만들었다고 전해진다.‘클렙시드라’는 크테시비우스 자신이 고안한 톱니바퀴와 펌프장치 등을 활용하여 이전에 존재하던 물시계의 단점을 보완한 획기적인 발명품으로, 기계장치에 부착된 인형이 시간을 가리키는 오토마타 자동물시계였다.
그리스 뿐만 아니라 고대 중국에서도 자동기계에 관한 기록 또는 얘기도 전해지고 있다. 주나라의 무왕(1023-957 BC) 시절에 얀시(Yan Shi)라는 기술자가 왕에게 사람 크기와 사람 모양을 가진, 기술적 일을 하는 기계를 보였다는 기록이 있고, 사마천의 <사기>에 따르면
"장인들로 하여금 자동으로 발사되는 기계장치가 된 쇠뇌를 만들게 하여, 접근하는 자가 있으면 즉시 발사되도록 했다."
라는 자동기계에 대한 기록이 남아 있다.
중세 시대에는 이슬람에서의 과학이 크게 발전해 많은 오토마타가 개발되었다. 8세기 중엽에는 바그다드에서 풍력으로 작동하는 동상이 만들어졌다. 이 동상은 "바그다드의 네 문마다 돔위에 얹혀져 바람이 불면 회전하였다"고 한다.
12세기의 이슬람 과학자 알 자자리는 음료 시중을 드는 자동인형, 자동문과 같은 자동 기계, 그리고 자동 기계로 된 악대 등을 개발하여 사용했다고 전해진다.
유럽에서는 오토마타의 발전에 중세 시대에는 이슬람에 비해 적었지만, 르네상스 시대 이후에 다시 눈에 띄게 발전하였다.
대표적인 예로 레오나르도 다 빈치(Leonardo da Vinci, 1452-1519)를 들 수 있는데, 비록 그 당시에 만들어지진 않았지만 가슴이 열리면 꽃이 나오는 사자 자동인형과 로봇 전투병의 스케치가 남아 있다.
동양에서도 이렇게 자동기계에 관한 관심을 기울인 사람들이 많았다. 조선에는 장영실(1390?~1450?)이 그 집합에 속한다. 그가 제작한 자격루, 옥루, 일성정시의 등의 자동시계를 비롯한 다양한 장치들은 모두 자동기계의 범주 내에 속한다. 중국에서는 11세기 북송시대 천문학자 소송이 12m 높이의 자동물시계 시계탑인 '수운의상대(水運儀象臺)'을 만들었다.

근대(16세기~19세기)

오토마타 또는 자동 기계는 16, 17세기 들어서부터 본격적으로 발전하기 시작했다. 17세기 유럽에 유행한 르네 데카르트(René Descartes, 1596~1650)의 기계론은 오토마타를 새로운 관점으로 보게 했으며, 오토마타에 대한 이론적, 철학적 토대를 마련하였다. 데카르트는 살아 있는 생명체가 사실상 복잡한 기계와 다를바 없다고 주장하였다.(그는 육체는 물질적인 것이고 영혼은 비물질적인 것이라고 하여 영혼의 존재를 부정하진 않았지만, 인간만이 영혼을 가지고 있다고 생각하였다고 한다.) 그에 따라 자연과 사물을 비교하는 방식의 중심엔 외형 대신 작동 방식이 들어서게 되었고, 그에 따라 자동기계는 더 활발히, 대중적으로 연구되고 개발되었다. 오토마타는 18세기 유럽에서 번창했는데, 대표적인 사람으론 기계오리를 만든 프랑스 발명가 자크 드 보캉송(Jacques de Vaucanson), 자동체스인형을 고안한 헝가리 발명가 볼프강 폰 켐펠렌(Wolfgang von Kempelen), 그리고 여러 자동인형을 만든 자크-드로즈(Pierre Jaquet-Droz)등이 있다.
한편 동양에서는 17세기 에도 시대에 일본으로 오토마타가 유럽으로부터 전해지기 시작했다. 일본에서는 오토마타를 '카라구리(Karakuri)'라고 부르며, 중국 등에서 온 물시계 제작 기술들의 영향을 받아 태엽과 톱티바퀴로 움직이는 자동인형들이 만들어졌다.

현대(20세기~)

현대에 들어서 오늘날까지도 여전히 오토마타 또는 자동기계는 하나의 예술 분야로서 폴 스푸너ㆍ피터 마키ㆍ아키오 니시다ㆍ키스 뉴스테와 같은 작가들에 의해 유지, 발전되고 있다.
그러나 유한 오토마타와 관련해서 현대에서 주목할 점은, 현대에 들어선 자동기계, 그리고 자동기계를 통해 생물을 모방, 창조하려는 시도가 컴퓨터 과학이라는 분야에서도 꽃피기 시작했고, 후에 컴퓨터 과학에서의 굳건한 분야로 자리잡았다는 점이다. 처음으로 유한 오토마타, 또는 유한 상태기계를 생각하게 된 사람들엔 생물학자들, 심리학자들, 수학자들, 공학자들, 그리고 최초의 컴퓨터 과학자들이 들어 있었다. 그들은, 이전의 자동기계들을 통해 본질적으로 구현해 내지 못한 인간의 특징인 '인간의 사고 과정(human thought process)'을 이론적 또는 실체적으로 구현해 내고자 수많은 시도를 하였다.

존 폰 노이만(John Von Neumann)

존 폰 노이만(John von Neumann, 1903년 12월 28일 ~ 1957년 2월 8일)은 헝가리 미국 독일 유태계의 수학자로서 양자물리학(quantum physics), 함수해석학(functional analysis), 집합이론(set theory), 컴퓨터 과학, 경제학과 많은 수학분야에 중요한 공헌을 하였다.
그는 생명체를 일종의 기계로 보았기 때문에 무기물인 기계도 자가 복제가 가능할 것이라고 생각했다. 노이만은 적어도 자신과 같은 정도의 복잡한 것을 만들어 내는 것이 가능하다는 것을 다음과 같은 방법으로 1948년에 논리적으로 증명하는 데 성공하였다.
1. 임의의 어떤 기계라도 만들 수 있는 만능제조 기계(Universal Machine) 을 설계한다.
2. UM 에 어떤 기계 M 을 만드는 프로그램을 담은 테이프 T(M) 을 넣는다면 UM 은 테이프 내용대로 기계 M 을 만들어 낼 것이다.

3. 만약 테이프 내용이 UM 을 만들라는 것일 경우 만능기계인 UM 은 테이프 내용 그대로 자신과 똑같은 또 하나의 UM 을 만들어 낼 것이다.
이 증명에서의 한가지 문제는 자가 복제 기계의 존재성은 만능 제조 기계의 존재성을 전제로 한다는 것이다. 노이만은 이 문제를 해결하기 위해 독일의 컴퓨터 과학자 콘라드 주세 (Konrad Zuse, 1910 ~ 95) 의 아이디어를 빌렸다. 노이만은 물리적 계의 이산모델로서 오토마타가 병렬로 연결된 계산공간을 고안해 낸다. 노이만은 결국 약 20만 개에 달하는 29개의 상태를 갖는 오토마타를 2 차원의 평면에 배열하여 자가 복제 기계를 만드는데 성공했다.
사후에 그의 공동연구자 아터 버크스가 논문으로 제작하여 출판하였고 (Theory of Self Reproducing Automata) 미국 IBM의 코드(E. F. Codd)에 의해 단순화되었고 실제로 구현되었다.

크리스토퍼 랭턴(Christopher G. Langton)

크리스토퍼 랭턴(1948~)은 유한 오토마타와 연관이 깊은 개념인 인공 생명(Artificial Life, Alife, AL)의 개념의 창시자라고 할 수 있다.
랭턴은 1987년 로스앨러모스 국립 연구소에서,"생명계의 합성과 시뮬레이션에 대한 워크샵"(Workshop on the Synthesis and Simulation of Living Systems, Artificial Life I)을 최초로 열었으며 이때 인공 생명이라는 단어를 만들었다.
랭턴은 인공 생명분야에 시뮬레이션과 계산적 모델, 그리고 철학적 문제까지 많은 부분 공헌하였다. 그는 정보, 계산과 번식에 관한 문제를 본질적으로 연관짓고, 기본적인 법칙을 정의하였다. 물리학의 법칙중 특히 상전이에 영감을 받아 셀룰러 오토마타의 몇가지 기본 개념과, 정량적 분석을 발전시켰다. 또, 특히 생물학에서, 정렬이 비정렬로부터 분리해 내는 임계점이 복잡계를 형성하는 데에 중요한 역할을 함을 제시하였다. 이런 그의 아이디어는, 비록 다른 근사법을 썼지만, Per Bak이나 James Crutchfield등에 의해서도 동시에 논의되었다.

진화 예술

진화 예술은 컴퓨터에 의해 만들어지는 예술의 한 형태로, 진화 디자인 가운데 예술적 창의성을 가장 큰 특징으로 갖는다. 진화 예술의 기본 배경은 사용자가 자연도태와 유사한 방식인 '선택'메커니즘을 통해 자신이 선호하는 작품을 만들고자 하는 것이다. 모든 진화 예술에서는 하나 이상의 부모 작품이 돌연변이 및 교배되어 다수의 자손 작품을 발생하게 되며, 적합도 평가에 기초해서 다음 세대를 구성할 작품이 선택된다. 가령, 미적인 이미지를 만드는 진화 예술 시스템은 임의의 값으로 초기화된 이미지 집단을 컴퓨터 화면에 보인다. 예술성을 평가할 기준을 컴퓨터 프로그램으로 만드는 데에는 아직 한계가 있기 때문에, 진화 예술가가 직접 이미지를 선택함으로써 자신이 선호하는 작품이 생존해서 더 좋은 작품으로 진화하도록 한다. 
진화 예술 시스템은 평가를 통해 선택된 이미지들을 돌연변이해서 다음 세대의 이미지를 만들어낸다. 이렇게 만들어진 이미지는 이전 세대의 것 보다는 미적으로 개선된 것이다. 진화 예술가는 다시 평가에 참여하고 진화계산에 의해 새로운 세대의 이미지가 발생한다. 이런 과정은 원하는 이미지가 만들어질 때까지 반복될 수 있다. 물론, 초기 집단에서 임의로 만들어진 이미지 대신에 이전에 만들었던 작품이나 아직 완성되지 않은 작품을 사용할 수도 있다. 진화 예술에서 진화알고리즘은 끊임없이 새로운 것을 발생시키기 위해 사용된다. 본질적으로 적합도를 평가할 수 있는 기준이 존재한다면 문자열로 표현할 수 있는 모든 것을 진화알고리즘에 의해 진화시킬 수 있다. 예술성을 평가할 기준을 컴퓨터 프로그램으로 만드는 데는 아직 한계가 있기 때문에, 진화 예술에서 작품에 대한 적합도 평가는 사용자가 한다. 즉, 프로그램이 다수의 예술작품을 발생하고 사용자가 자신의 선호도에 따라 작품을 선택하면, 재결합을 통해 새로운 세대의 작품이 발생하게 된다.

진화 음악

진화 음악은 진화 예술에서 소리를 다루는 부분이다. 진화 음악은 진화 알고리즘으로부터 생성되는 알고리즘적인 음악이다. 진화 음악은 개인, 또는 여러 사람이 만들어낸 소리(멜로디 등)나 그 소리의 일부분을 사용하거나 완전히 랜덤하게 시작된다. 그 다음 계산적인 생물학적 과정(예를 들어 자연선택, 돌연변이, 재결합)을 사용하여 생산된 소리가 더 음악적이 되도록 만든다. 
진화 음악의 합성은 소리를 생성하거나 악기를 종합하는 기술과도 연관되어 있다. 진화 음악은 사용자나 청중들에게 음악의 기능이 적합하도록 만들어주는 상호작용적인 진화 알고리즘을 사용하지만, 아직 계산적으로 음악의 품질을 측정하기는 어려움이 있다. 그러나 음악의 품질에 대한 자동 계산의 정확성을 높이는 것에 대한 연구도 현재 이루어지고 있다. 진화 계산 기술은 조화나 반주 작업에도 사용된다. 이러한 진화 연산 작업을 구현하는 기술로는 유전 알고리즘이나 유전 프로그래밍이 있다.

자연발생론

자연발생설(自然發生說, Abiogenesis)은 생명체가 부모 없이 스스로 생길 수 있다는 가설이지만, 인공생명에서 다루는 자연발생론이란 생명의 기원에 대한 알고리즘적 시뮬레이션을 의미한다.

유한 오토마타와 셀룰러 오토마타

폰 노이만은 1948년 그의 논문 Theory of Self-reproducing Automata에서 스스로 자기 자신을 복제할 수 있는 로봇 모델을 구상했다. 이러한 로봇은 환경 인식 부분, 활동 부분, 에너지원 등 다양한 부분들로 이루어져 있었는데, 폰 노이만이 로봇을 구상하면서 직면한 과제는 바로 그러한 로봇이 적절한 환경에서 필요한 것들을 모아서 자기 자신의 복제품으로 만들도록 하는 것이었다.
이러한 모델 세계의 복잡성 때문에 과제를 손쉽게 해결하지 못 하고 있던 폰 노이만에게, 로스 알라모스 국립 연구소 동료였던 Stanislaw Ulam은 별개의 부분으로 이루어진 연속적인 공간 대신 간단한 유한 오토마타로 이루어진 균일하고 구별된 공간(uniform discrete space of simple finite automata)을 사용하라고 제안했다. 바로 이러한 공간 하나를 바로 셀룰러 오토마톤(Cellular Automaton)이라고 부른다. 아이디어를 얻은 폰 노이만은 처음엔 3차원의 셀룰러 공간을 구상했으나, 2차원 셀룰러 공간이 더 단순하고 편리함을 깨닫고 2차원 셀룰러 공간을 택했다. 그는 각각의 셀을 차지하는 29개의 상태를 가지는 유한 오토마타를 정의했고, 그가 '기관'(organ)이라고 부른 다양한 유한 연산 구조를 만들었다. 그의 목표는 이것들을 어떻게 조합하여 자가 복제 오토마타를 이론적으로 만들 것인가였지만, 그는 말년에 병에 걸렸기 때문에 이 연구를 완성시킬 순 없었다고 한다.
Arthur W. Burks는 Creative Uses of Logic in the Invention of the Electronic Computer("전자 컴퓨터의 발명에서의 논리의 창의적 활용")에서 비록 폰 노이만이 EDVAC의 구조를 설계하는 데에는 성공하고 자가 복제 오토마타를 완성시키진 못 했지만, 폰 노이만의 구상은 실용적으로 응용될 수 있는 부분이 많으며, 자가 복제 가능한 시스템들의 집합의 중요한 특징에 대한 추상적 모델이라고 평가하면서 그 의의를 밝히고 있다.
이렇게 시작된 셀룰러 오토마타의 개념은 정의할 때부터 이미 유한 오토마타의 성질을 갖고 있었을 뿐만 아니라 유한 오토마타와 역사적, 기술적으로 관련이 있는 인공생명과도 밀접한 관계에 있다. 특히 폰 노이만의 셀룰러 오토마타(von Neumann's cellular automata)는 최초의 '부드러운' 인공 생명 중 하나로 꼽히고 있으며, 폰 노이만과 같은 해에 인공 생명과 연관이 있는 논문을 썼던 Norbert Wiener는 1946년에 Arturo Rosenblueth와 함께 쓴 논문 "The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle"에서 흥분될 수 있는 매질 내에서의 셀룰러 오토마타를 디자인했다고 한다.

UML 상태 기계

통합 모델링 언어(UML, 영어: Unified Modeling Language)는 상태 기계를 나타낼 수 있는 표기법을 갖고 있다. UML 상태 기계 는 고전적인 유한 상태기계의 이점은 살리면서, 한계를 극복할 수 있다. UML 상태 기계는 동작와 전이의 연장선상에서 위계적으로 중첩된 상태와 직교 영역이라는 개념을 도입하였다. UML 상태 기계는 밀리 모델과 무어 모델의 특징을 동시에 가진다. 행위와 전이에서, 밀리 모델처럼 시스템의 상태와 이벤트의 발생 모두에 의존적이며, 또 무어 모델처럼 상태보다는 전이에 더 관련깊은 진입 동작과 퇴장 동작에 의존적이기도 하다.

다른 상태 다이어그램

이 외에도 유한 상태 기계를 표현할 수 있는 방법은 많다.

하드웨어적 응용

디지털 회로에서, 유한 오토마타는 설계 가능 논리 소자, 프로그래머블 로직 컨트롤러, 논리 회로 그리고 플립플롭 또는 전자계전기를 사용하여 구축될 수 있다. 즉, 하드웨어적 응용에는 상태 변수를 저장할 프로세서 레지스터, 상태 전이 함수를 결정할 여러가지 논리들과 유한오토모타의 출력을 결정할 논리들이 필요하다.

텍스트 필터링

자바나 C#, SQL등의 프로그래밍 언어에서 결정적 유한 오토마타를 사용하여 지정된 글자가 적합한지 판별할 수 있다. 예를 들어 이메일의 기본적인 형식은 "문자열"+"@"+"도메인" 인데, 주어진 문자열과 이 형식이 일치하는치 판별할 수 있다. 자바에서는 java.util.regex 패키지에서, C#은 System.Text.RegularExpressions 네임스페이스에서, SQL언어는 직접 정규 문법을 사용할 수 있다. 사용자가 정규 문법을 사용해서 만든 코드는 각각의 프로그래밍 언어의 컴파일러에서 자동으로 결정적 유한 오토마타로 변환되어 사용된다.