13. 오토마타, 형식 언어, 문법

오토마타(Automata)

- 자동기계 장치라는 뜻

- 일반적으로 입력 장치, 출력 장치, 저장 장치, 제어 장치를 가지고 있음

 

오토마타의 특성

1) 오토마타는 입력 데이터를 읽을 수 있는 입력 기능을 가지고 있다

입력 데이터는 입력 파일에 쓰여져 있는 알파벳상의 스트링들로 이루어져 있는데, 입력 파일은 네모꼴의 셀(cell)들로 이루어져 있으며 각 셀에는 오직 하나의 심볼만 존재

2) 오토마타는 특정 형태의 출력 기능을 가지고 있다

0이나 1의 출력을 생성할 수 있으며 인식(accept) 또는 기각(reject)의 출력도 생성

3) 오토마타는 무한개의 셀들로 이루어진 임시 저장장치를 가질 수 있다

각 셀은 하나의 심볼만을 가질 수 있는데, 오토마타는 작동에 따라 셀들의 내용을 읽어내거나 변경할 수 있음

4) 오토마타는 유한개의 내부 상태를 제어할 수 있는 제어 장치를 가지고 있다

이것의 제어에 따라 상태가 변화될 수 있음

 

오토마타의 기본 개념

- 오토마타는 이산적인 시간 단위로 작동됨을 기본 가정으로 함

- 어느 특정 시각에 제어 장치는 특정의 상태에 놓여 있음

- 입력 기능은 입력 파일상의 어떤 특정한 심볼을 읽음

- 제어 장치의 다음 상태는 전이 함수(transition fuction)에 의해 결정됨

- 전이 함수는 현재의 제어 상태, 입력 심볼, 임시 저장 장치 내의 정보들에 의해 결정됨

 

결정적 오토마타(deterministic automata)

:전이에 의한 다음 상태가 현재의 형상에 따라 유일하게 결정되는 오토마타이다

즉, 현재의 내부상태, 입력 심볼, 임시 기억 장치에 관한 정보를 알면 오토마타의 다음 행동을 정확히 예측할 수 있다

 

비결정적 오토마타(nondeterministic automata)

: 현재의 형상에서 2가지 이상의 이동도 가능한 오토마타로서, 가능한 이동의 집합을 예측할 수 있을 뿐

 

오토마타는 출력여부에 따라 인식기와 트랜스듀서로 나누어짐

- 인식기(accepter) : 주어진 입력에 대해 인식하거나 기각할 수 있ㄴ느 기능만을 가짐

- 트랜스듀서(transducer) : 인식이나 기각의 기능 외에 출력도 할 수 있는 오토마타 모델

 

유한 상태 시스템(Finite Stae Machine : FSM) : 유한개의 상태를 가진 오토마타

 

유한 오토마타(Finite Automata : FA)

- 이산적인 입력과 출력을 가지는 시스템의 수학적 모형

- 유한한 개수의 내부 상태들을 가지고 있는데, 시스템의 상태는 다음에 들어올 입력에 대한 시스템의 행동을 결정하는데 필요한 과거의 정보들을 요약함

- 인식기(recognizer)로서의 유한 오토마타를 고찰함

- 유한 오토마타의 주요 특징으로는 임시 저장 장치를 가지지 않는다는 점과 입력 테이프는 단지 읽힐 수만 있으며 그 내용이 변경될 수 없다

- 기능은 작동 과정에서 정보를 기억하는데 있어서 상당한 제약을 받게 됨

 

유한 제어(finite control)

- 유한 오토마타의 입력과 상태들을 제어함

- 유한 오토마타는 여러 종류의 오토마타들 중에서 가장 단순한 형태로서 입력과 유한 제어를 가진 유한 오토마타를 나타냄

- 유한 오토마타는 유한한 상태들의 집합과 전이 함수(transition function)들의 집합으로 구성됨

- 전이란 상태에서 상태로의 변화

- 입력에 따라 상태는 항상 변할 수 있으며, 원래의 상태로 다시 돌아가는 전이도 있을 수 있음

 

전이 다이어그램(transition diagram)

- 각 유한 오토마타마다 전이 다이어그램이라 불리는 방향이 있는 그래프는 전이 다이어그램과 같이 그려짐

 

정규 언어(regular language)

- 유한 오토마타는 전이 방법에 따라 결정적 유한 오토마타와 비결정적 유한 오토마타로 구분됨

 

오토마타 이론에서 가장 중요한 3가지 개념

- 언어(language), 문법(grammar), 오토마타(automata)를 들 수 있음

1) 언어 : 자연어(natural language), 형식 언어(formal language)

2) 문법

: 컴퓨터에 사용되는 문법은 배커스와 나우어에 의해 체계화된 배커스-나우어 표기법(BNF)과 푸시다운 오토마타(PDA)에 의한 문맥자유 문법(CFG)로 구분