[컴퓨터사무자동] 오토마타

목차

-오토마타(Automata)
오토마타 이론과 컴퓨터 관련 학문
오토마타와 관련된 3가지 개념
유한 오토마타
오토마타의 응용
문법(grammar)과 언어(language)
튜링머신(Turing machine)
촘스키 포함 관계(Chomsky Hierarchy)

본문내용

10.1 오토마타(Automata)
‘오토마타’(automata)란
인간이 행하는 어떤 목적에 합당한 약간 복잡한 동작을 기계적인 제어기구에 의하여 실시하는 장치.
디지틀 컴퓨터의 수학적인 모델인 오토마톤(automaton)의 복수형으로서 로봇 또는 자동기계라고도 한다. 어원은 자동기계라는 뜻의 그리스어이다.
입력장치, 출력장치, 저장장치, 제어장치를 가지고 있으므로 현대적인 디지틀 컴퓨터가 작동하는 이론적인 메카니즘이라 볼 수 있다.


오토마타의 필수적인 특성

1. 오토마타는 입력 데이타를 읽을 수 있는 기능을 가지고 있다.
입력 데이터 : 입력 화일(input file)에 쓰여져 있는 알파벳상의 스트링들로 이루어져 있다.
유한 오토마타의 경우 입력 파일에 있는 내용을 읽는 것은 가능하지만 변경은 불가능하다.
입력화일은 네모꼴의 셀(cell)들로 이루어져 있는데 각 셀에는 오직 하나의 심볼씩만 존재한다. 입력은 입력 파일의 왼쪽에서 오른쪽으로 심볼을 하나씩 차례로 읽게 되며 파일의 끝까지 읽게 된다.

2. 오토마타는 특정 형태의 출력 기능을 가지고 있다. 0이나 1의 출력을 낼 수도 있으며 ‘인식’(accept) 또는 ‘기각’(reject)의 출력도 생성할 수 있다.

3. 오토마타는 무한개의 셀들로 이루어진 임시 저장장치(storage device)를 가질 수 있다. 각 셀은 하나의 심볼만을 가질 수 있는데 오토마타는 따라 셀들의 내용을 읽어 내거나 변경할 수 있다.

4. 오토마타는 유한개의 내부 상태(internal states)를 제어할 수 있는 제어장치(control unit)를 가지고 있다. 이것의 제어에 따라 상태가 변화될 수 있다.

참고 자료

없음