Automata  Theory

 

오토마타 이론 (Automata Theory) 은 계산 능력이 있는 추상기계 와 오토마타, 그리고 그 기계를 이용해서 풀 수 있는 문제들을 연구하며, 이론 컴퓨터 과학의 한 분야이며 이산수학의 하위 과목이다. .... 오토마타 (Automata) 또는 튜링 기계 (Turing Machine) 와 같은 것을 수학적으로 표현함으로써 유한상태 기계 (Finite State Machine) 를 연구하는 컴퓨터과학의 한 분야이다. 일반적인 오토마타가 어떻게 만들어지며 어떻게 작동하는 지를 연구한다. ..... (Wikipedia : Automata Theory)

paper

오토마타 (automaton) 란 디지털 컴퓨터에 대한 추상적 모델이며, 모든 오토마타들은 몇 가지 필수적인 기능들을 갖는다. 우선 오토마타는 입력을 받아들이는 장치를 갖는다. 입력은 주어진 알파벳에 대한 문자열이고 입력 파일 (input file) 에 저장되며, 오토마타는 이를 읽을 수는 있지만 변경할 수는 없다. 입력 파일은 셀 단위로 구분되며, 각 셀은 하나의 심볼을 저장할 수 있다. 입력 장치는 (EOF 조건을 검사함으로써) 입력 문자열의 마지막을 감지할 수 있다. 오토마타는 어떤 형태로든 출력을 생성할 수도 있다. 또한, 오토마타는 임시 기억장소 (storage)를 가질 수 있다. 이 기억장소는 무한 개의 셀들로 구성되어 있으며, 각 셀은 주어진 알파벳(이는 반드시 입력 알파벳과 같을 필요는 없다) 내의 한 심볼을 저장할 수 있다. 오토마타는 제어 장치 (control unit) 를 가진다. 이 제어 장치는 유한 개의 내부 상태 (internal state) 들 중 한 상태에 있을 수 있으며, 미리 정해진 규칙에 따라 상태를 바꿀 수 있다 ......... (Peter Linz 2001)

오토마톤 이론이란 오토마톤을 연구하는 학문이지만, 다른 표현 방식을 빌린다면 ‘대상의 어떤 기능에 주목하여, 입력과 내부 출력 각 신호의 상호관계를 수학모델로 옮기고, 이 모델을 수학적으로 고찰 ·결론을 유도한다. 그리고 이 유도된 결론을 다시 원래의 대상에 꼭 들어맞춰서 해석한다고 하는 일련의 과정의 일부 또는 전부’에 관계되는 것이다. 그리고 대상의 구성요소의 성질 등에는 그리 관여하지 않는다. 이와 같은 입장을 취함으로써 새로운 시야가 열리며, 미시적인 견지로부터는 끄집어낼 수 없는 많은 유용한 결론이 기대된다 .......

term :

오토마타 이론 (Automata Theory)    오토마타 (Automata)    유한상태 기계 (Finite State Machine)   튜링 기계 (Turing Machine)     계산이론 (Theory of Computation)    계산 복잡도 이론 (Computational Complexity Theory)       문맥자유 문법 (Context Free Grammar)      인공생명 (Artificial Life)   인공지능 (Artificial Intelligence)    세포자동자 (Cellular Automata)

site :

Wikipedia : Automata Theory    위키백과 : 오토마타 이론    

video :

컴퓨테이션 이론, 2014년 2학기 : 건국대학교 : 남원홍 ... 동영상 23개

Theory of Computation - Fall 2011 (Course) : UCDavis : Dan Gusfield, 2012/12/11 .... Playlist 22 : text ... Introduction to the Theory of Computation (Michael Sipser)

 

Introduction to the Theory of Computation : Coderisland : Shai Simonson, 2010/05/07 .... Playlist 129