유한 오토마톤(Finite automaton)

유한 오토마톤은 기억이 유한한 기계입니다. 상태 몇 개와 '이 상태에서 이 기호를 읽으면 저 상태로'라는 전이 규칙만 있고, 입력을 왼쪽부터 한 글자씩 읽으며 상태를 옮깁니다. 다 읽었을 때 받아들임 상태(이중 원)에 있으면 입력을 받아들이고, 아니면 거부합니다. 되돌아가 다시 읽을 수도, 어디에 적어 둘 수도 없다는 점에서 테이프에 쓰고 오가는 튜링 기계⁠(Turing machine)⁠보다 훨씬 약합니다. 그림으로는 상태가 꼭짓점⁠(vertex)⁠이고 전이가 기호를 단 화살표인 방향 그래프입니다. 자판기, 지하철 개찰구, 신호등 제어, 문서에서 낱말 찾기가 모두 이런 기계입니다.

기계를 로 바꾸고 한 글자씩 따라가 보세요.

이진수가 3의 배수⁠(multiple)⁠인지 가리는 기계는 수 전체가 아니라 나머지만 기억합니다. 지금까지 읽은 이진수가 m이면 다음 비트 b를 읽은 뒤의 수는 $2m + b$입니다(진법⁠, positional notation⁠). 그러니 m을 3으로 나눈 나머지⁠(remainder)⁠ r만 알면 다음 나머지 $(2r + b) \bmod 3$을 알 수 있고(모듈러 연산⁠, modular arithmetic⁠), 상태 셋이면 충분합니다. 수를 끌어 바꿔 보세요: . 입력이 그 수의 이진수()로 바뀝니다. 같은 방법으로 어떤 수 k의 배수든 상태 k개로 가려낼 수 있습니다.

이런 기계가 받아들이는 문자열을 모두 모은 집합⁠(set)⁠을 정규 언어⁠(regular language)⁠라고 합니다. 1951년 미국 논리학자 스티븐 클리니는 유한 오토마톤이 인식하는 언어가 정확히 이어 쓰기·고르기·되풀이로 적는 정규 표현식으로 나타낼 수 있는 언어임을 보였습니다(보고서 1951, 출판 1956). 'ab로 끝나는 문자열'은 $(a|b)^*ab$입니다. 'a나 b를 아무렇게나 몇 번 쓴 뒤 ab'라는 뜻입니다. 두 기계를 나란히 돌리면 합집합⁠(union)⁠과 교집합⁠(intersection)⁠을, 받아들임 상태를 뒤집으면 여집합⁠(complement)⁠을 인식합니다. 그래서 정규 언어 둘에 집합의 연산⁠(set operations)⁠을 하면 다시 정규 언어가 됩니다. 이것을 정규 언어가 집합의 연산에 대해 닫혀 있다고 말합니다. 한 기호를 읽고 갈 수 있는 곳이 여러 갈래인 기계도 생각할 수 있습니다. 갈래 가운데 하나라도 받아들임 상태에 닿으면 받아들이는 이런 기계를 비결정적 오토마톤⁠(nondeterministic automaton)⁠이라 하는데, 힘은 보통의 유한 오토마톤과 같습니다(마이클 라빈과 데이나 스콧, 1959년. 두 사람은 이 연구로 1976년 튜링상⁠(Turing Award)⁠을 받았습니다). 상태 k개인 비결정적 기계는 상태들의 부분집합⁠(subset)⁠을 새 상태로 삼아 결정적 기계로 바꿀 수 있고, 그래서 상태가 최대 $2^k$개(멱집합⁠, power set⁠)로 늘어날 수 있습니다.

한계도 분명합니다. a를 n개 쓰고 b를 n개 쓴 문자열 $a^n b^n$만 받아들이는 기계는 없습니다. 상태가 k개라면 a를 0개부터 k개까지 읽은 k + 1가지 경우 가운데 두 경우, 예를 들어 a를 i개 읽은 경우와 j개 읽은 경우(i ≠ j)는 같은 상태에 있어야 합니다(비둘기집 원리⁠, pigeonhole principle⁠). 그 뒤로 b를 i개 읽으면 $a^i b^i$는 받아들이고 $a^j b^i$는 거부해야 하는데, 같은 상태에서 같은 글자를 읽으니 두 경우를 구별할 수 없습니다. 괄호 짝 맞추기도 같은 이유로 안 됩니다. 기계에 스택(접시 더미처럼 맨 위에만 넣고 꺼낼 수 있는 기억 장치)을 하나 붙이면 이런 중첩을 다룰 수 있습니다. 여는 괄호를 만날 때마다 접시를 하나 얹고 닫는 괄호를 만날 때마다 하나 꺼내면 짝이 맞는지 알 수 있습니다. 이런 기계를 푸시다운 오토마톤⁠(pushdown automaton)⁠이라 하고, 갈림길을 허용한(비결정적) 푸시다운 오토마톤이 인식하는 언어가 정확히 문맥 자유 문법⁠(context-free grammar)⁠의 언어입니다. 이 층들이 촘스키 위계⁠(Chomsky hierarchy)⁠이고, 유한 오토마톤은 맨 아래층입니다.

이어지는 곳. 유한 오토마톤은 입력을 한 번 훑으면 반드시 멈추므로, 튜링 기계와 달리 정지 문제⁠(halting problem)⁠가 생기지 않습니다. 전이마다 확률⁠(probability)⁠을 붙이면 마르코프 연쇄⁠(Markov chain)⁠가 되고, 상태는 숨어 있고 상태가 내놓는 기호만 보이면 은닉 마르코프 모델⁠(hidden Markov model)⁠이 됩니다. 1943년 신경생리학자 워런 맥컬러와 논리학자 월터 피츠는 뇌의 뉴런을 입력이 문턱⁠(threshold)⁠을 넘으면 켜지는 스위치로 본 신경망⁠(neural network)⁠ 모형을 제안했는데, 뉴런이 유한 개이니 이것은 유한 상태 기계입니다. 클리니의 정규 표현식도 이 신경망이 알아볼 수 있는 입력을 정리하다가 나왔습니다. 1958년 로젠블랫은 이런 인공 뉴런이 가중치⁠(weight)⁠를 예에서 배우게 한 퍼셉트론⁠(perceptron)⁠을 발표했습니다. 대수 쪽에서 보면, 어떤 언어를 유한 오토마톤이 알아볼 수 있는 것은 그 언어의 구문 모노이드(낱말을 이어 붙이는 연산을 언어가 구별하는 만큼만 남긴 모노이드⁠(monoid)⁠)가 유한할 때와 정확히 같습니다. 에일렌베르크는 이 대응을 따라 정규 언어의 부류들을 유한 모노이드의 부류들로 분류하는 이론을 세웠습니다. 입력에 따라 상태를 선형으로 갱신하는 상태 공간 모형⁠(state space model)⁠을 이 눈으로 보면 한계가 드러납니다. 1의 개수의 홀짝(패리티⁠, parity⁠)은 두 상태 오토마톤⁠(automaton)⁠ 하나로 알아볼 수 있습니다. 이것을 선형 갱신으로 흉내 내려면 1을 읽을 때마다 부호를 뒤집는 것, 곧 고유값⁠(eigenvalue)⁠ −1 같은 음의 고유값이 필요합니다. Mamba처럼 갱신 행렬⁠(matrix)⁠의 고유값이 늘 0과 1 사이인 모형은 부호를 뒤집을 수 없어서, 유한한 정밀도⁠(precision)⁠에서는 임의로 긴 입력의 패리티를 풀지 못한다는 것이 2024년에 증명되었습니다.