오토마타

혹시라도 동명의 웹툰을 찾아오셨다면 그것에 대해서는 오토마타(웹툰) 문서를 참조하십시오.

자동으로 움직이는 기계에 대해서는 오토마톤 문서를 참조하십시오.

Automata

1 개요

오토마타는 그리스어의 '자동'을 의미하는 단어에서 유래한 영단어로, 계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들에 대한 학문적 접근으로 컴퓨터 과학 분야에 컴파일러의 설계, 파싱, 정형화 등에 있어서 중요한 역할을 담당하는 이론이다.

A survey for Modeling and Control of of Hybrid System 에 따르자면 "오토마톤이란 수학적으로 추상화된 개념으로 쓰일 경우, 자동기계를 기능적인 견지에서 모델화하여, 외부로부터의 자극, 입력신호,에 대응하여 내부의 상태가 변화하고, 그리고 신호 또는 동작의 형태로 외부에 출력하는 것으로 ‘대상의 어떤 기능에 주목하여, 입력과 내부 출력 각 신호의 상호관계를 수학모델로 옮기고, 이 모델을 수학적으로 고찰 ·결론을 유도한다.

그리고 이 유도된 결론을 다시 원래의 대상에 꼭 들어 맞춰서 해석한다고 하는 일련의 과정의 일부 또는 전부’ 에 관계되는 것이다." 라고 정의할 수 있다.

2 동작 방식

입력은 유한한 문자열로 주어진다. 오토마타는 유한한 내부상태를 가지며 무한한 저장공간을 가질 수도 있다. 저장공간은 다양한 형태로 주어질 수 있고 이것에 따라서 오토마타의 종류가 나뉜다. 오토마타는 한 번에 하나의 입력 문자를 읽을 수 있다.

이 때 읽은 문자와 현재의 내부상태, 그리고 저장공간에 적힌 값에 따라서 다음의 내부상태가 바뀐다. 이 과정에서 저장공간에 적힌 값을 바꿀 수 있다. 이런 과정을 멈출 때까지 진행한다.

오토마타의 내부상태 중에는 승인상태라고 부르는 것들이 있다. 오토마타가 동작을 멈추었을 때 승인상태에 있다면 이 오토마타는 그때의 입력 문자열을 '인식'한 것이다. 어떤 문자열들을 인식하느냐 인식하지 않느냐를 결정하므로 하나의 오토마타는 문자열을 인식하는 것, 인식하지 않는 것으로 구분하는 '문제를 푼다'고 할 수 있다. 어떤 문제를 풀 수 있냐가 오토마타의 능력이 된다.

사실 위에서 언급한 것은 오토마타 중 결정적 오토마타에 한정된 것이다. 비결정적 오토마타에서는 각 동작마다 유한한 가지의 분기점으로 갈 수 있다. 그리고 각 분기점마다 다시 분기점으로 갈라진다.

그리고 하나의 분기점에서라도 오토마타가 인식을 한다면 이것은 인식한 것으로 간주한다! 다시 말해서 한 번에 여러개의 경우의 수를 한꺼번에 해볼 수 있는 것이다.

3 종류

3.1 유한 상태 기계

유한 상태 기계는 내부상태 이외의 저장 공간을 갖지 않는 오토마타이다. 입력 문자열이 주어지면 이것을 하나씩 읽으면서 내부상태를 바꿔나간다. 저장공간이 없기에 아주 간단한 특성을 가진다.

알고리즘을 나타낼 때 이 유한 상태 기계를 이용하면 좋다. 각 내부상태를 단계로 생각하여 어떤 단계에서 어떤 단계로 이동할지를 모두 표시해 놓는 것이다. 촘스키 언어 계층에서 정규언어(Regular Language)와 대응된다.

3.2 스택 오토마타

내부상태 이외에 스택(자료구조)으로 된 저장 공간을 갖는 오토마타이다. 입력 문자열이 주어지면 이것을 하나씩 읽으면서 내부상태를 바꿔나간다. 동시에 스택 맨 위의 적힌 내용을 읽고 바꾸거나 지우거나 새로 쓸 수 있다.

스택은 무한하므로 유한한 저장공간을 가졌던 유한 상태 기계에 비해 다양한 일이 가능하다. 예를 들어 유한 상태 기계는 a와 b의 개수가 같은 문자열인지 확인하는 일을 하지 못했다.

왜냐하면 지금까지 나온 a 개수나 b 개수를 기록해 둬야 이것을 할 수 있을텐데 유한 상태 기계는 저장공간이 유한해서 이것을 하지 못한다. 반면에 스택 오토마타는 이 작업을 할 수 있다. 스택 오토마타는 문맥 자유 언어(Context Free Language)와 대응된다.

스택 오토마타의 작업이 결정적이냐 비결정적이냐에 따라 결정적 스택 오토마타냐 비결정적 스택 오토마타이냐가 나뉜다. 여기서 비결정적 스택 오토마타는 할 수 있는 일이 많고 아주 유용하게 쓰인다. 컴파일러에서도 활용되며 심지어는 생성언어학에서 인간의 문법 구조를 분석하는 것과도 관련이 있다.

3.3 튜링 머신

이제는 무한 1차원 테이프를 저장 공간을 갖는다. 스택 오토마타가 스택 맨 위의 원소만 활용할 수 있던 것과 달리 무한 테이프 위를 왔다갔다 하면서 테이프의 모든 내용을 항상 활용할 수 있다.

게다가 유한 상태 기계와 스택 오토마타가 주어진 문자열을 하나씩 읽으면서 작동했던 것과 달리 이제는 입력도 테이프에 적혀있는 채로 주어진다. 테이프를 좌우로 왔다갔다 하면서 동작하기에 입력을 순서대로 읽는 것이 아니며 동작이 끝나지 않게 될 수도 있다. 유한 상태 기계와 스택 오토마타가 컴퓨터가 할 수 있는 일 중 일부를 모델링했다면 튜링 머신은 (지금까지의) 컴퓨터가 할 수 있는 모든 일을 모델링 할 수 있다. 자세한 것은 튜링 머신 참조.

3.4 그 외

저장 공간을 큐(자료구조)로 갖는 오토마타, 저장 공간의 크기가 얼마 이하로 정해져서 나오는 오토마타 등 다양한 오토마타를 생각해 볼 수 있다.

동작 방식도 아예 확률적으로, 심지어 양자적으로 움직이는 오토마타도 많이 연구된다.

4 세포 자동자

Cellular Automata.

오토마타 중 특수한 경우로 존 폰 노이만이 처음으로 제시한 개념이다.

격자와 같은 구조에 있는 단위(세포)들이 있고 매 시간 단위마다 이 세포들은 주변에 있는 세포의 상태에 따라 자신의 상태를 바꾼다. 폰 노이만은 이것을 이용하여 스스로 복제하는 생명체와 같은 구조를 연구했고 DNA, RNA와 유사한 메커니즘으로 자기 복제하는 구조를 실제로 제시했다.

이 개념이 널리 알려진 것은 콘웨이의 생명 게임 때문이다. 콘웨이는 이 세포 자동자를 통해 흥미로운 구조를 많이 만들어냈고 폰 노이만이 제시했던 것보다 훨씬 간단한 자기 복제 구조를 찾아냈다.

백문이 불여일견. 항목을 참조하면 세포 자동자의 실제 예를 그림으로 확인할 수 있다. 이것 외에도 2차원이 아닌 1차원의 세포 자동자 등 수많은 세포 자동자가 연구되었다.