오토마타 이론
위키백과 ― 우리 모두의 백과사전.
오토마타 이론은 추상 기계와 그 기계가 풀 수 있는 문제들을 연구하는 컴퓨터 과학의 한 분야이다. 오토마타 이론에서 다루는 추상 기계를 흔히 오토마타(영어: automata, 복수형) 또는 오토마톤(영어: automaton, 단수형)이라 부른다. 형식 언어 이론과 밀접히 연관되어 있으며, 오토마타 이론에서 다루는 오토마타는 보통 오토마타가 인식할 수 있는 형식 언어의 종류에 따라 분류된다.
![]() |
이 문서는 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해갑시다. |
오토마타 이론: 형식 언어 및 형식 문법 | |||
---|---|---|---|
촘스키 위계 | 형식 문법 | 형식 언어 | 최소한의 자동장치 |
Type-0 | (무제약) | 순환 열거 언어 | 튜링 기계 |
(무제약) | 순환 언어 | 판정자 | |
Type-1 | 문맥 의존 문법 | 문맥 의존 언어 | 선형유한 오토마타 |
Type-2 | 문맥 무관 문법 | 문맥 무관 언어 | 내리누름 오토마타 |
Type-3 | 정규 문법 | 정규 언어 | 유한 오토마타 |
각 언어 및 문법은 바로 윗 줄 언어 및 문법의 진부분집합이다. |