오토마타 이론
위키백과 ― 우리 모두의 백과사전.
오토마타 이론은 추상 기계와 그 기계가 풀 수 있는 문제들을 연구하는 컴퓨터 과학의 한 분야이다. 오토마타 이론에서 다루는 추상 기계를 흔히 오토마타(영어: automata, 복수형) 또는 오토마톤(영어: automaton, 단수형)이라 부른다. 형식 언어 이론과 밀접히 연관되어 있으며, 오토마타 이론에서 다루는 오토마타는 보통 오토마타가 인식할 수 있는 형식 언어의 종류에 따라 분류된다.
 |
이 문서는 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |
| 오토마타 이론: 형식 언어 및 형식 문법 | |||
|---|---|---|---|
| 촘스키 위계 | 형식 문법 | 형식 언어 | 최소한의 자동장치 |
| Type-0 | (무제약) | 순환 열거 언어 | 튜링 기계 |
| (무제약) | 순환 언어 | 판정자 | |
| Type-1 | 문맥 의존 문법 | 문맥 의존 언어 | 선형유한 오토마타 |
| Type-2 | 문맥 무관 문법 | 문맥 무관 언어 | 내리누름 오토마타 |
| Type-3 | 정규 문법 | 정규 언어 | 유한 오토마타 |
| 각 언어 및 문법은 바로 윗 줄 언어 및 문법의 진부분집합이다. | |||
|
|
|
|---|---|
| 수학적 기초 | 수리논리학 · 집합론 · 정수론 · 그래프 이론 · 형 이론 · 범주론 · 수치해석 |
| 계산 이론 | 오토마타 이론 · 계산 가능성 이론 · 계산 복잡도 이론 · 양자 계산 이론 |
| 알고리즘 & 자료 구조 | 알고리즘 해석 · 알고리즘 · 알고리즘 설계 · 자료구조 · 계산 기하학 |
| 프로그래밍 언어 & 컴파일러 | 구문 분석 · 컴파일러 · 인터프리터 · 프로그래밍 언어 · 순차적 프로그래밍 · 객체지향 프로그래밍 |
| 병행,병렬 & 분산 시스템 | 병행 컴퓨팅 · 분산 컴퓨팅 · 병렬 컴퓨팅 · 그리드 컴퓨팅 |
| 소프트웨어 공학 | 요구 분석 · 소프트웨어 설계 · 컴퓨터 프로그래밍 · 형식수법 · 소프트웨어 테스팅 · 소프트웨어 개발 |
| 시스템 아키텍처 | 컴퓨터 아키텍처 · 마이크로아키텍처 · 운영체계 |
| 통신 & 네트워크 | 컴퓨터 오디오 · 라우팅 · 네트워크 토플로지 · 암호학 |
| 데이터베이스 | 데이터 마이닝 · RDBMS · SQL |
| 인공 지능 | 자동추론 · 전산언어학 · 컴퓨터 비전 · 진화연산 · 기계학습 · 자연언어 처리 · 로봇학 |
| 컴퓨터 그래픽 | Visualization · 영상 처리 |
| 인간과 컴퓨터 상호 작용 | Computer accessibility · 사용자 인터페이스 · 착용 컴퓨터 · 유비쿼터스 컴퓨팅 · 가상현실 |
| 계산과학 | 인공생명 · 생물정보학 · 인지과학 · 계산화학 · 계산론적 신경과학 · 계산물리학 · 수치해석 · Symbolic mathematics |
