[계산이론] 오토마타 간략한 개념

Automata

디지털 컴퓨터의 추상화된 모델.

input file에 기록된 alphabet들로 이루어진 string을 input으로 입력받는다고 가정. (수정 불가)

input file은 cell로 구분되고, 각 cell은 하나의 symbol을 담고 있다.

input 메커니즘은 왼쪽에서 오른쪽으로 input string의 symbol을 한 번에 하나씩 읽어들이고 EOF 조건을 인식하여 input string의 끝을 감지할 수 있다.

기계는 output을 생성할 수도 있다.

cell 갯수 제한이 없는 임시 storage 장치를 가질 수 있고 하나의 cell은 하나의 symbol만 가질 수 있다.

기계는 storage cell의 내용을 읽고 수정할 수 있다.

오토마타는 control unit을 가지고 이는 유한한 internal states 중 하나에 있을 수 있다. 또한 정해진 방식에 따라 state를 변화시킬 수 있다.

오토마타의 동작 단계는 discrete한 시간에서 이루어진다고 가정한다.

주어진 시점에서 control unit은 어떠한 internal state에 있고, input 메커니즘은 input 파일의 특정 symbol을 스캔한다.

control unit의 다음 기 internal state는 next-state 또는 transition function에 의해 결정된다.

• transition function은 현재 state, 현재 input symbol, 현재 임시 storage의 정보를 받아서 다음 state로 변환한다.
• 한 시점에서 다음 시점으로 transition될 때 output을 출력하거나 임시 storage의 정보가 바뀔 수 있다.

configuration이라는 용어는 control unit, input file, 임시 storage의 특정 상태를 종합하여 부를 때 사용된다.

오토마타의 특정 configuration에서 다음 configuration으로의 transition을 move라고 부른다.