오토마타는 어떤 사건, 즉 기호에 어떤 방식으로든 반응하는 추상적인 수학적 대상입니다.
오토마톤은 초기 상태, 가능한 상태들의 집합, 기호들의 집합, 그리고 현재 상태와 기호의 쌍에 대해 오토마톤이 어떤 새로운 상태로 전이해야 하는지를 결정하는 함수로 정의됩니다.
오토마타는 다양한 많은 과정과 계산을 기술할 수 있습니다. 예를 들어, 컴퓨터 자체도 오토마타 구현의 특수한 경우입니다. 상태는 메인 메모리와 레지스터의 내용이고, 이벤트는 사용자와의 상호작용이며, 전이 규칙은 아키텍처입니다.
또 다른 예로는 셀룰러 오토마타가 있으며, 독자 여러분은 존 콘웨이의 「라이프 게임」을 통해 이미 알고 계실 수도 있습니다. 이 게임에서 오토마톤의 상태와 전이 규칙은 각 개별 셀의 상태로 정해지며, 규칙은 격자 전체에 한꺼번에 적용됩니다.
이 절에서는 문자열 문제의 맥락에서 오토마타의 구체적인 응용을 살펴보겠습니다.