위키백과 ― 우리 모두의 백과사전.
 |
이 문서는 편집 지침에 맞춰 다듬어야 합니다. 이 문서를 정리해 주세요. |
 |
이 문서는 위키백과의 품질 기준을 확보하기 위해 위키화 작업이 필요합니다.
적절한 내부 링크를 추가하거나 문서의 배치를 변경해주세요. |
오토마타 이론(영어: Automata Theory)은 추상 기계와 그 기계가 풀 수 있는 문제들을 연구하는 컴퓨터 과학의 한 분야이다. 오토마타 이론에서 다루는 추상 기계를 흔히 오토마타(automata, 복수형) 또는 오토마톤(automaton, 단수형)이라 부른다. 형식 언어 이론과 밀접히 연관되어 있으며, 오토마타 이론에서 다루는 오토마타는 보통 오토마타가 인식할 수 있는 형식 언어의 종류에 따라 분류된다.
오토마타 (automaton) 란 디지털 컴퓨터에 대한 추상적 모델이며, 모든 오토마타들은 몇 가지 필수적인 기능들을 갖는다. 우선 오토마타는 입력을 받아들이는 장치를 갖는다. 입력은 주어진 알파벳에 대한 문자열이고 입력 파일 (input file) 에 저장되며, 오토마타는 이를 읽을 수는 있지만 변경할 수는 없다. 입력 파일은 셀 단위로 구분되며, 각 셀은 하나의 심볼을 저장할 수 있다. 입력 장치는 (EOF 조건을 검사함으로써) 입력 문자열의 마지막을 감지할 수 있다. 오토마타는 어떤 형태로든 출력을 생성할 수도 있다. 또한, 오토마타는 임시 기억장소 (storage)를 가질 수 있다. 이 기억장소는 무한 개의 셀들로 구성되어 있으며, 각 셀은 주어진 알파벳(이는 반드시 입력 알파벳과 같을 필요는 없다) 내의 한 심볼을 저장할 수 있다. 오토마타는 제어 장치 (control unit) 를 가진다. 이 제어 장치는 유한 개의 내부 상태 (internal state) 들 중 한 상태에 있을 수 있으며, 미리 정해진 규칙에 따라 상태를 바꿀 수 있다.(Peter Linz 2001)
오토마톤 이론이란 오토마톤을 연구하는 학문이지만, 다른 표현 방식을 빌린다면 ‘대상의 어떤 기능에 주목하여, 입력과 내부 출력 각 신호의 상호관계를 수학모델로 옮기고, 이 모델을 수학적으로 고찰 ·결론을 유도한다. 그리고 이 유도된 결론을 다시 원래의 대상에 꼭 들어맞춰서 해석한다고 하는 일련의 과정의 일부 또는 전부’에 관계되는 것이다. 그리고 대상의 구성요소의 성질 등에는 그리 관여하지 않는다.[출처 필요]
[편집] 같이 보기
[편집] 참고 링크
