DataBaser.Net: Terms

2 오토마타(Automata) #

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

오토마타는 이산 시간(discrete time) 단위로 운영되는 것을 가정한다. 임의의 주어진 시간에 제어 장치는 어떤 내부 상태에 있게 되며, 입력 장치는 입력 파일의 특정 심볼을 읽어들인다. 다음 단계에서의 제어 장치의 내부 상태는 다음-상태 함수(next-state function) 또는 전이 함수(transition function)에 의하여 결정된다. 이 전이 함수는 현재 상태, 현재의 입력 심볼, 현재 임시 기억장소에 저장된 내용 등에 따라 다음 상태를 결정한다. 한 단계에서 다음 단계로 전이가 발생하는 동안 출력이 생성되거나 임시 기억장소의 내용이 변화될 수 있다. 형상(configuration)이라는 용어는 제어 장치와 입력 파일, 그리고 임시 기억장소의 상태를 종합하여 언급할 때 사용한다. 오토마타가 한 형상으로부터 다음 형상으로 전이하는 것을 이동(move) 이라 한다.

이러한 일반적인 모델은 모든 오토마타에 적용된다. 어떤 경우에도 유한-상태 제어장치(finite-state control)는 공통적이지만, 출력을 생성하는 방법이나 임시 기억장소와 관련한 성질은 오토마타마다 차이가 있다. 임시 기억장소의 성질은 각 형태의 오토마타에 대해 커다란 영향을 주게 된다.

오토마타를 결정적 오토마타(deterministic automata)와 비결정적 오토마타(nondeterministic automata) 로 구분할 필요가 있다. 결정적 오토마타에서는 각 이동이 현재의 형상에 의해 유일하게 결정된다. 즉, 오토마타의 내부 상태, 입력, 그리고 임시 기억장소의 내용 등이 알려지면 그 오토마타의 이후 행동을 정확히 예측할 수 있게 되는 것이다. 비결정적 오토마타에서는 그렇지 않다. 비결정적 오토마타는 각 단계에서 여러 가지 이동이 가능하며, 따라서 정확히 하나의 가능한 행동만을 예측하기 보다는 가능한 행동들의 집합을 예측할 수 있을 뿐이다. 여러 형태의 오토마타에 대한 결정적 오토마타와 비결정적 오토마타간의 관계는 우리가 공부하는 데 있어서 중요한 역할을 할 것이다.

출력이 단순히 "yes" 또는 "no"로 제한되어 있는 오토마타를 인식기(accepter)라 한다. 입력 문자열이 주어졌을 때 인식기는 오로지 그 문자열을 승인(accept)하거나 거부(reject)하는 역할만을 수행한다. 이보다 더 일반적인 오토마타로 임의의 문자열을 출력으로 생성할 수 있는 오토마타를 변환기(transducer)라 부른다.

출처: 네이버 지식인(http://kin.naver.com/qna/detail.nhn?d1id=1&dirId=104&docId=66523364&qb=7Jik7Yag66eI7YOA&enc=utf8§ion=kin&rank=1&sort=0&spq=0)
한글오토마타 C++(http://codepedia.tistory.com/42)
한글오토마타(http://minimonk.tistory.com/1406)

Contents

1 CR, LF #

2 오토마타(Automata) #