이산수학 - 오토마타[Automata]개념정리

이산수학 - 오토마타[Automata]개념정리

정의

오토마타는 이산시간 동안 주어진 입력에 의존해 문제를 푸는 [수학적 기계 :계산능력이 있는 추상기계(자동기계)]이다.

---

일반적으로 오토마타는 유한한 상태를 갖고, 입력을 받아 입력에 따라 일정하게 상태를 전이하며 출력을 내놓는다.

이는 알고리즘이 요구하는것, 즉 계산문제를 해결할 능력과 같다. 계산문제는 일반적으로 오토마타의 능력에 맞게 결정문제로 환산되며, 이 때 추상기계와 형식언어, 형식문법은 불가분의 관계가 된다. 따라서 오토마타는 언어와 문법과 같은 계층분류를 갖는다.

오토마타는 컴퓨터구조 설계와 컴파일러 설계, 파싱, 정형모델의 정형 검증등의 중요한 요소이다.