오토마타 이론

오토마타 이론은 추상적인 기계와 오토마타, 그리고 이를 이용해 해결할 수 있는 계산 문제를 연구하는 학문이다. 오토마타라는 단어는 그리스어 아프토마토스(αὐτόματος)에서 유래되었으며, 이는 “스스로 행동하고, 스스로 의지하며, 스스로 움직이는 것”을 의미한다. 오토마톤(복수형은 오토마타)은 미리 정해진 작업 순서를 스스로 따르는 추상적인 계산 장치이다. 상태 수가 유한한 오토마톤를 유한 상태 기계 또는 유한 상태 머신이라고 한다.