[오토마타] 3. 오토마톤

 

오토마톤은 디지털 컴퓨터에 대한 추상적인 모델이다.

디지털 컴퓨터는 기본적으로 입력이 주어지면 저장공간을 활용하여 이를 적절히 처리한 뒤 결과물을 내보낸다.

 

이때 입력 데이터는 수학적 편의를 위해서 '알파벳 심볼에 의해 정의된 문자열' 이라고 정의한다. (꼭 이래야만 하는 것은 아니다)

그리고 인풋 파일은 무한한 길이의 테이프로부터 문자열을 읽어들일 수 있다고 생각한다.

이 테이프는 여러개의 셀로 구성되어 있으며, 각 셀에는 알파벳 심볼 하나가 저장된다.

 

디지털 컴퓨터는 내부적으로 연속된 시간이 아니라, 이산적인 시간 체계로 동작하며,

각 시간마다 인풋 파일의 왼쪽에서 오른쪽을 향해 한번에 하나의 셀(심볼)을 읽어들인다.

그리고 End-Of-File (EOF) 신호를 통해 문자열의 끝을 감지할 수 있도록 기계가 만들어져 있다고 하자.

 

이 기계는 temporary storage를 갖는데, 이 저장 공간은 크기가 무한하다고 가정한다.

그리고 인풋 파일처럼 여러 개의 셀로 이루어져 있으며, 이 공간에 대해서는 값을 읽을 수도, 수정할 수도 있다.

(화살표가 인풋 파일과 달리 양방향이다.)

 

입력 데이터를 처리하는 control unit 의 경우, 내부적으로 유한한 상태(state)를 갖는다.

컴퓨터가 꺼져있다가 켜지면, 초기 상태에서 출발해서 이산적인 시간이 흐름에 따라 다른 상태로 변화할 수 있다.

또한 상태를 갖는다는 것은 내부적으로 별도의 저장공간을 갖고 있음을 의미한다.

 

 

이를 기반으로 transition function 을 생각할 수 있다.

트랜지션 함수는 특정 시점에서의 contorl unit의 상태, input symbol, storage 정보가 주어질 때 어떤 상태로 변화하는지 / 스토리지 값을 어떻게 바꾸는지 기술한 함수이다.

 

그리고 이 시점에서의 제어유닛 상태, 인풋 심볼, 저장공간 정보를 묶어서 Configuration 이라고 한다.

마지막으로 Configuration 에서 다른 Configuration으로 변화하는 것을 Move 라고 한다.

 

오토마톤 기계는 다양한 기준에 따라 분류할 수 있다.

 

먼저 특정 상태에서의 Move 개수에 따라

결정적인 (Deterministic) 기계는 Move 가 유일하고,

비결정적인 (Non-Deterministic) 기계는 다양한 Move 가 있을 수 있다.

 

기계의 출력에 따라서는

만약 출력이 이진화되어있다면 Acceptor 라고 하고, (yes / no 로 대답하는 경우)

출력이 string으로 다양하게 나온다면 Transducer 라고 부른다.

 

 

 

---

오토마톤 적용

C언어에서는 다음과 같은 규칙의 문법이 있다.

 

식별자는 문자, 숫자, _ 의 나열인데, 숫자로는 시작할 수 없고, 대소문자를 모두 사용할 수 있다고 한다.

그렇다면 자연어로 기술된 이 규칙을 지난 글에서 정리한 Grammar로 어떻게 나타낼 수 있을까?

프로그래밍언어론에서 정리했던 BNF 규칙처럼 다음과 같은 문법으로 나타낼 수 있다.

 

 

이 문법은 C언어 식별자의 productions 를 보여준다.

여기에서 < > 안에 들어있는 문자열은 모두 '변수'를 의미한다.

그리고 < > 로 감싸져있지 않은 문자열은 모두 '터미널' 이다.

특히 <id> 는 start variable 이다.

 

이 문법을 이번 글에서 정리한 오토마톤을 사용해 나타내면 위와 같이 나타낼 수 있다.

 

 

 

동그라미는 '상태' 를 나태내고, 각 화살표는 상태의 이동을 나타낸다.

화살표 위의 문자는 그 상태로 변화하는 조건(그 순간의 input symbol)을 나타낸다.

 

1번 상태는 들어오는 화살표가 하나 있는데, 이 기호는 1번 상태가 초기 상태임을 나타낸다.

1번 상태에서 숫자가 들어오면 3번 상태로 가고, 문자나 _ 가 들어오면 2번 상태로 간다.

그리고 2, 3번 상태에서는 어떤 입력이 들어와도 현재 상태를 유지한다.

 

이 기계는 최종적으로는 내 현재 상태가 2번 변수명이 맞다고 대답하고, 1 또는 3이면 변수명이 아니라고 대답하는 기계가 된다.