오토마타 이론(영어: Automata Theory)계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 컴퓨터 과학의 분야이다.여기서 추상 기계를 오토마타(automata, 복수형) 또는 오토마톤(automaton, 단수형), 즉 자동 기계라고 부른다.이 이름은 '자동'을 의미하는 그리스어 'αὐτόματα'에서 유래하였다. 일반적으로 오토마타는 적어도 유한한 상태를 갖고, 입력을 받아 입력에 따라 일정하게 상태를 전이하며, 출력을 내놓는다. 이는 알고리즘이 요구하는 것, 즉 계산 문제를 해결할 능력과 같다. 계산 문제는 일반적으로 오토마타의 능력에 맞게 결정 문제로 환산되며, 이 때 추상 기계와 형식 언어, 형식 문법은 불가분의 관계가 된다. 따라서 오토마타는 언어와 문법과 ..