오토마타
Automata
1. 개요
오토마타(Automata)는 '자동'을 의미하는 그리스 단어인 Αυτόματα에서 유래한 용어로, 계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들에 대해 학문적으로 접근한 컴퓨터 과학 분야이다. 컴파일러의 설계, 파싱, 정형화 등에 있어서 중요한 역할을 담당하는 이론이다.
A survey for Modeling and Control of Hybrid System[1]에 따르자면 "오토마톤이란 수학적으로 추상화된 개념으로 쓰일 경우, 자동기계를 기능적인 견지에서 모델화하여, 외부로부터의 자극, 입력신호에 대응하여 내부의 상태가 변화하고, 그리고 신호 또는 동작의 형태로 외부에 출력하는 것으로 ‘대상의 어떤 기능에 주목하여, 입력과 내부 출력 각 신호의 상호관계를 수학모델로 옮기고, 이 모델을 수학적으로 고찰 ·결론을 유도한다. 그리고 이 유도된 결론을 다시 원래의 대상에 꼭 들어 맞춰서 해석한다고 하는 일련의 과정의 일부 또는 전부’ 에 관계되는 것이다." 라고 정의할 수 있다.
2. 동작 방식
입력은 유한한 문자열로 주어진다. 오토마타는 유한한 내부상태를 가지며 무한한 저장공간을 가질 수도 있다. 저장공간은 다양한 형태로 주어질 수 있고 이것에 따라서 오토마타의 종류가 나뉜다. 오토마타는 한 번에 하나의 입력 문자를 읽을 수 있다.
이때 읽은 문자와 현재의 내부상태, 그리고 저장공간에 적힌 값에 따라서 다음의 내부상태가 바뀐다. 이 과정에서 저장공간에 적힌 값을 바꿀 수 있다. 이런 과정을 멈출 때까지[2] 진행한다.
오토마타의 내부상태 중에는 승인상태라고 부르는 것들이 있다. 오토마타가 동작을 멈추었을 때 승인상태에 있다면 이 오토마타는 그때의 입력 문자열을 '인식'한 것이다. 어떤 문자열들을 인식하느냐 인식하지 않느냐를 결정하므로 하나의 오토마타는 문자열을 인식하는 것, 인식하지 않는 것으로 구분하는 '문제를 푼다'고 할 수 있다. 어떤 문제를 풀 수 있냐가 오토마타의 능력이 된다.
사실 위에서 언급한 것은 오토마타 중 결정적 오토마타에 한정된 것이다. 비결정적 오토마타에서는 각 동작마다 유한한 가지의 분기점으로 갈 수 있다. 그리고 각 분기점마다 다시 분기점으로 갈라진다. 그리고 하나의 분기점에서라도 오토마타가 인식을 한다면 이것은 인식한 것으로 간주한다! 다시 말해서 한 번에 여러 개의 경우의 수를 한꺼번에 해볼 수 있는 것이다.
결정적 오토마타와 비결정 오토마타는 계산 능력의 차이가 있는 경우도 있고 없는 경우도 있다. 예를들면 결정적 유한 상태 기계와 비결정적 유한 상태 기계는 계산 능력이 동등하다. 그러나 결정적 푸시다운 오토마타와 비결정적 푸시다운 오토마타는 계산 능력이 다르다. 그러나 결정적 오토마타는 그 자체로 비결정적 오토마타에 단 한가지로만 분기하는 특이 케이스이기 때문에 계산 능력에 차이가 있는 경우 비결정적 오토마타가 그 능력이 더 크다.
3. 종류
3.1. 유한 상태 기계
유한 상태 기계는 내부상태 이외의 저장 공간을 갖지 않는 오토마타이다. 입력 문자열이 주어지면 이것을 하나씩 읽으면서 내부상태를 바꿔나간다. 저장공간이 없기에 아주 간단한 특성을 가진다.
알고리즘을 나타낼 때 이 유한 상태 기계를 이용하면 좋다. 각 내부상태를 단계로 생각하여 어떤 단계에서 어떤 단계로 이동할지를 모두 표시해 놓는 것이다.
결정적이든 비결정직이든 유한 상태 기계는 계산 능력이 동등하며 촘스키 언어 계층에서 정규언어(Regular Language)와 대응된다.
또한, 비결정적 유한 상태 기계를 결정적 유한 상태 기계로 변환할 수 있는 알고리즘이 존재한다. 결정적 오토마타는 위에서 서술하였듯이 비결정적 오토마타에서 무조건 하나의 상태로만 분기하는 특이 케이스이기 때문에 결정적 유한 상태 기계는 그 자체로 비결정적 유한 상태 기계이며 변환 알고리즘이 필요 없다.
대표적인 어휘분석기 생성기인 Lex나 Flex는 이것을 응용한 것이다. 또한, 정규표현식도 이것을 응용한 것이다.
3.2. 푸시다운 오토마타(Push-Down Automata, PDA)
내부상태 이외에 스택으로 된 저장 공간을 갖는 오토마타이다. 입력 문자열이 주어지면 이것을 하나씩 읽으면서 내부상태를 바꿔나간다. 동시에 스택 맨 위의 적힌 내용(Top)을 읽고 바꾸거나 지우거나 새로 쓸 수 있다.
스택의 크기는 무한하므로 유한한 저장공간을 가졌던 유한 상태 기계에 비해 다양한 일이 가능하다. 예를 들어 유한 상태 기계는 a와 b의 개수가 같은 문자열인지 확인하는 일을 하지 못한다.[3] 반면, 푸시다운 오토마타는 이 작업을 할 수 있다.
위에서 서술하였듯이 결정적 푸시다운 오토마타와 비결정적 푸시다운 오토마타는 계산 능력이 다르다. 결정적 푸시다운 오토마타는 결정적 문맥 자유 언어(Deterministic Context Free Language)와 대응되며, 비결정적 푸시다운 오토마타는 문맥 자유 언어(Context Free Language)와 대응된다.
여기서 비결정적 푸시다운 오토마타는 할 수 있는 일이 많고 아주 유용하게 쓰인다. 컴파일러에서도 활용될 수 있으며[4] 심지어는 생성언어학에서 인간의 문법 구조를 분석하는 것과도 관련이 있다.
3.3. 튜링 머신
이제는 무한 1차원 테이프[5]를 저장 공간으로 갖는다. 스택 오토마타가 스택 맨 위의 원소만 활용할 수 있던 것과 달리 무한 테이프 위를 왔다갔다 하면서 테이프의 모든 내용을 항상 활용할 수 있다.
게다가 유한 상태 기계와 스택 오토마타가 주어진 문자열을 하나씩 읽으면서 작동했던 것과 달리 이제는 입력도 테이프에 적혀있는 채로 주어진다. [6] 테이프를 좌우로 왔다갔다 하면서 동작하기에 입력을 순서대로 읽는 것이 아니며 동작이 끝나지 않게 될 수도 있다.[7] 유한 상태 기계와 스택 오토마타가 컴퓨터가 할 수 있는 일 중 일부를 모델링했다면 튜링 머신은 (지금까지의) 컴퓨터가 할 수 있는 모든 일을 모델링 할 수 있다. 사실상 현존하는 컴퓨터의 근간 그 자체. 자세한 것은 튜링 머신 참조.
튜링머신은 결정적 버전과 비결정적 버전의 계산 능력이 같으며 촘스키 위계에서 재귀적 열거 가능 언어(Recursively enumerable language)와 동등하다.
알고리즘을 유효한 입력에 정확한 답을 출력하고 곧바로 정지하는 튜링머신으로 정의하기도 한다.[8]
튜링머신과 동일한 계산능력을 가지는 언어나 기계는 튜링 완전하다고 말한다. 그러나 수학적으로 튜링머신은 무한한 저장공간을 가지는데 실제 컴퓨터는 유한한 저장공간을 가지므로 원칙적으로는 튜링 완전하지 않다. 대신 이렇게 유한한 저장공간을 가지는 경우에는 느슨하게 튜링 완전하다고 말한다.
3.4. 그 외
저장 공간을 큐로 갖는 오토마타, 저장 공간의 크기가 얼마 이하로 정해져서 나오는 오토마타 등 다양한 오토마타를 생각해 볼 수 있다.
동작 방식도 아예 확률적으로, 심지어 양자적으로 움직이는 오토마타도 많이 연구된다.
게임 니어:오토마타의 "오토마타"는 이 용어에서 따왔다.
4. 세포 자동자
Cellular Automata.
오토마타 중 특수한 경우[9]로 존 폰 노이만이 처음으로 제시한 개념이다.
격자와 같은 구조에 있는 단위(세포)들이 있고 매 시간 단위마다 이 세포들은 주변에 있는 세포의 상태에 따라 자신의 상태를 바꾼다. 폰 노이만은 이것을 이용하여 스스로 복제하는 생명체와 같은 구조를 연구했고 DNA, RNA와 유사한 메커니즘으로 자기 복제하는 구조를 실제로 제시했다.[10]
이 개념이 널리 알려진 것은 콘웨이의 생명 게임 때문이다. 콘웨이는 이 세포 자동자를 통해 흥미로운 구조를 많이 만들어냈고 폰 노이만이 제시했던 것보다 훨씬 간단한 자기 복제 구조를 찾아냈다.
백문이 불여일견. 항목을 참조하면 세포 자동자의 실제 예를 그림으로 확인할 수 있다. 이것 외에도 2차원이 아닌 1차원의 세포 자동자 등 수많은 세포 자동자가 연구되었다.
[1] Labinaz, Gino, Mohamed M. Bayoumi, and Karen Rudie. "A survey of modeling and control of hybrid systems." Annual Reviews in Control 21 (1997): 79-92. 의 번역본[2] 입력 문자열이 다 떨어지거나 혹은 더 이상 움직이지 않는다고 정해진 내부상태에 이르면 멈춘다.[3] 왜냐하면 지금까지 나온 a 개수나 b 개수를 기록해 둬야 이것을 할 수 있을 텐데 유한 상태 기계는 저장공간이 유한해서 이것을 하지 못한다.[4] 그러나 실제 대부분의 컴파일러 구현에서는 문맥 자유 문법 파싱의 비교적 느린 시간복잡도 때문에 백 트레킹이 필요 없고 선형적인 시간복잡도의 파싱 알고리즘을 가지는 LL문법이나 LR, SLR, LALR 문법 등이 사용된다. 이것들은 문맥 자유 문법의 부분집합이며 현재의 입력과 k개의 look-ahead가 있을때 오직 단 하나의 생성 규칙을 적용할 수 있는 문법이기 때문에 선형적인 시간복잡도에서 처리가 가능한 것이다.[5] 실제로 운영 체제는 사용자에게 무한하다고 생각할 수 있을 만큼 넓은 메모리 영역을 공간을 빌릴 때마다 랜덤으로 할당해 준다.[6] 실제로 운영 체제에서 프로그램을 실행하면 프로그램의 정보 전체가 메모리로 올라간다.[7] 정지 문제, 무한 루프.[8] 이 정의에 따르면 답을 내놓지 못하고 무한루프에 빠지는 것은 알고리즘이 아니다.[9] 사실 위의 엄밀한 정의에 의하면 일반적인 오토마타와는 조금 다르다. 그러나 시간 단위에 따라 자동적으로 변한다는 점에서 오토마타와 유사하다.[10] 이 당시는 유전자 복제의 메커니즘이 발견되기 이전이었다!