| 오토마타 관련 분야 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1. 개요
Automata오토마타는 추상적인 계산기로, 정해진 규칙에 따라 입력을 읽으면서 내부의 상태를 바꾸고 결과를 출력하는 기계의 수학적 모델이다. 단어 'automaton'은 '스스로 작동하는'을 뜻하는 그리스어 단어 'αυτόματος'에서 유래했으며, 한국어에서는 보통 복수형 'automata'를 음차한 '오토마타'로 지칭한다.
오토마타 이론은 이런 오토마타를 바탕으로 문제의 계산가능성, 효율성 등을 다루는 학문이며 오토마타와 밀접한 연관이 있는 형식문법, 언어까지도 다룬다. 오토마타 이론은 컴퓨터과학의 근간이 되는 분야라고 할 수 있으며 계산이론, 인공지능, 컴퓨터 구조 설계, 컴파일러 설계, 파싱, 정형검증 등의 분야에서 중요한 역할을 담당한다.
2. 설명
2.1. 언어
오토마타의 입력은 유한한 문자열로 주어진다. 알파벳 [math(\Sigma)]는 입력 문자열에서 사용될 수 있는 글자의 집합이다. 이 문서에서는 특별한 이유가 없다면 이진 알파벳 [math(\Sigma = \left \{ 0,\ 1 \right \})]을 사용하기로 한다. 언어 [math(L)]은 알파벳으로 만들 수 있는 모든 유한한 문자열의 집합의 부분집합이다.일반적으로 오토마타가 푸는 문제는 "주어진 문자열이 특정 조건을 만족하는가?"와 같은 형태인데, 이는 "주어진 문자열이 특정 언어에 속하는가?"라는 문제로 생각할 수 있다. 특정 언어에 대해 어떤 오토마타 [math(M)]이 이 문제를 풀 수 있다면 [math(M)]은 해당 언어를 받아들인다고 한다. 오토마타 [math(M)]이 받아들이는 이 언어를 기호로 [math(L \left ( M \right ))]으로 표기한다. 오토마타가 받아들일 수 있는 언어의 종류가 다양할수록 계산능력이 좋다고 표현한다.
2.2. 문법
(형식)문법이란 언어 내의 문자열이 만들어지는 과정을 일반화한 것으로, 시작 변수를 포함한 변수와 생성규칙으로 구성된다. 예시로 한국어를 생각하자. 한국어 문자열 "고양이의 발이 부드럽다."는 아래와 같이 생성할 수 있을 것이다.| 한국어의 생성규칙[1] |
- (시작 변수) [math(\rightarrow)] (주어) (서술어). [math(|)] ...
- (주어) [math(\rightarrow)] (명사구)(주격 조사) [math(|)] ...
- (서술어) [math(\rightarrow)] (형용사) [math(|)] ...
- (명사구) [math(\rightarrow)] (명사구)(관형격 조사) (명사구) [math(|)] (명사) [math(|)] ...
- (명사) [math(\rightarrow)] 고양이 [math(|)] 발 [math(|)] ...
- (주격 조사) [math(\rightarrow)] 이 [math(|)] 가
- (관형격 조사) [math(\rightarrow)] 의
- (형용사) [math(\rightarrow)] 부드럽다 [math(|)] ...
- ... ||
| 문자열 생성 예시[2] |
|
(시작 변수) [math(\Rightarrow)] (주어) (서술어). [math(\Rightarrow)] (명사구)(주격 조사) (서술어). [math(\Rightarrow)] (명사구)(관형격 조사) (명사구)(주격 조사) (서술어). [math(\Rightarrow)] (명사)(관형격 조사) (명사구)(주격 조사) (서술어). [math(\Rightarrow)] 고양이(관형격 조사) (명사구)(주격 조사) (서술어). [math(\Rightarrow)] 고양이의 (명사구)(주격 조사) (서술어). [math(\Rightarrow)] 고양이의 (명사)(주격 조사) (서술어). [math(\Rightarrow)] 고양이의 발(주격 조사) (서술어). [math(\Rightarrow)] 고양이의 발이 (서술어). [math(\Rightarrow)] 고양이의 발이 (형용사). [math(\Rightarrow)] 고양이의 발이 부드럽다. |
문법은 생성규칙의 조건에 따라 정규문법, 문맥자유 문법, 문맥민감 문법, 무제한 문법 등으로 구분할 수 있다. 노엄 촘스키는 앞의 문법 4개와 각 문법이 생성할 수 있는 언어의 관계를 이론화했는데 이를 촘스키 위계\[Chomsky hierarchy]라고 한다.
2.3. 오토마타의 동작
오토마타는 기본적으로 입력을 읽는 헤드와 유한 개의 내부 상태를 가지며, 종류에 따라 추가적으로 저장 공간을 가질 수도 있다. 오토마타는 한 번에 글자 하나를 읽으며, 읽은 글자와 자신의 내부 상태, 추가적인 저장 공간에서 읽은 내용에 따라 내부 상태를 바꾸고, 새로 저장할 내용을 저장 공간에 쓴다. 이를 멈출 때까지 반복한다.내부 상태 중에는 오토마타가 멈추도록 하는 상태가 존재하거나 오토마타의 종류에 따라 언젠간 무조건 멈추는 경우에는 상태 중에 승인 상태가 존재한다. 전자는 오토마타가 정지 상태에 도달해 작동을 멈추면 입력받은 문자열을 받아들이는 것이고, 후자는 오토마타가 멈췄을 때 내부 상태가 승인상태라면 입력받은 문자열을 받아들이는 것이다.
2.4. 오토마타의 결정성
오토마타는 결정적\[deterministic] 오토마타와 비결정적\[nondeterministic] 오토마타로 분류할 수 있다. 결정적 오토마타는 각 단계에서 하나의 상황만을 가질 수 있고, 비결정적 오토마타는 각 단계에서 하나 이상의 상황을 가질 수 있다. 쉽게 말해 계산 중 분기점이 나타난 경우, 결정적 오토마타는 한 번에 한 경우만 확인할 수 있지만, 비결정적 오토마타는 한 번에 여러 경우를 확인할 수 있다. 각 단계마다 최대 [math(n)]가지의 분기점이 있다면 [math(m)]단계만에 최대 [math(n ^m)]가지의 경우를 확인할 수 있다는 뜻이다. 그리고 확인한 모든 경우 중에 입력 문자열을 받아들이는 경우가 단 하나라도 존재한다면 해당 문자열을 받아들인다.결정적 오토마타와 비결정적 오토마타는 종류에 따라 계산능력이 같을 수도 다를 수도 있다. 다른 구조가 서로 같다면 결정적 오토마타는 비결정적 오토마타의 특수한 경우이니 계산능력이 다르면 비결정적 오토마타가 더 다양한 언어를 받아들일 수밖에 없다. 하지만 결정성의 차이에도 불구하고 계산능력이 같은, 즉 받아들일 수 있는 언어의 종류가 같은 경우도 있다.
3. 종류
3.1. 유한 상태 기계
유한 상태 기계\[finite state machine] 또는 유한 오토마타\[finite automaton]는 내부 상태 외의 저장 공간을 갖지 않는 오토마타이다. 저장 공간이 없기 때문에 가장 간단한 형태의 오토마타라고 할 수 있다. 입력 문자열을 순서대로 하나씩 읽으면서 읽은 글자와 내부 상태에 따라 내부 상태를 바꾸면서 작동한다. 문자열을 모두 읽었을 때 내부 상태가 승인 상태라면 해당 문자열을 받아들이고, 그렇지 않다면 이를 받아들이지 않는다.유한 상태 기계의 경우, 결정적 유한 상태 기계와 비결정적 유한 상태 기계의 계산능력이 동일하다. 즉, 임의의 비결정적 유한 상태 기계에 대해 동일한 언어를 받아들이는 결정적 유한 상태 기계가 존재하며, 이를 구하는 알고리즘도 존재한다.
유한 상태 기계가 받아들이는 언어의 집합은 정규문법\[regular grammar]에서 생성할 수 있는 정규언어\[regular language]의 집합과 같다. 언어 [math(L _1 = \left \{ 0 ^n | n \in \N _0 \right \})][3]은 정규언어의 예시 중 하나이다.
유한 상태 기계는 오토마타 이론 관련 수업에서 가장 먼저 다루는 가장 간단한 오토마타인데도 매우 유용해 다른 분야에서도 많이 사용된다. 대표적인 예시로 논리회로가 있는데, 순차적 논리회로는 유한 개의 저장 공간을 가지므로 이를 내부 상태로 생각해 유한 상태 기계로 표현할 수 있다. 정규 표현식이나 어휘분석기 등에서도 유한 상태 기계를 사용할 수 있다.
3.2. 푸시다운 오토마타
푸시다운 오토마타(push-down automaton)는 내부 상태 외의 저장 공간으로 무한한 크기의 스택을 갖는 오토마타이다. 이제는 입력 문자열을 순서대로 하나씩 읽음과 동시에 스택에 필요한 정보를 읽거나 쓰면서 내부 상태를 바꾸면서 작동하고, 이에 따라 유한 상태 기계보다 더 폭넓은 언어를 받아들일 수 있다. 문자열을 모두 읽었을 때 내부 상태가 승인 상태라면 해당 문자열을 받아들이고, 그렇지 않다면 이를 받아들이지 않는다.푸시다운 오토마타의 경우, 결정적 푸시다운 오토마타와 비결정적 푸시다운 오토마타의 계산능력이 다르다. 비결정적 푸시다운 오토마타가 받아들이는 언어의 집합은 문맥자유 문법\[context-free grammar]에서 생성할 수 있는 문맥자유 언어\[context-free language]의 집합과 같고, 결정적 푸시다운 오토마타가 받아들이는 언어의 집합은 결정적 문맥자유 언어\[deterministic context-free language]의 집합과 같다. 정규언어의 집합은 결정적 문맥자유 언어의 집합의 진부분집합이고, 결정적 문맥자유 언어의 집합은 문맥자유 언어의 집합의 진부분집합이다. 언어 [math(L _2 = \left \{ 0 ^n 1 ^n | n \in \N _0 \right \})][4]는 결정적 문맥자유 언어의 예시 중 하나이며, 언어 [math(L _3 = \left \{ w \in \Sigma ^* | w = w ^\mathrm {T} \right \})][5]은 문맥자유 언어의 예시 중 하나이다.
프로그래밍 언어는 문맥자유 언어라고 할 수 있기 때문에 관련 분야에 푸시다운 오토마타를 활용할 수 있다. 예를 들어 코드를 컴파일하는 과정에서 코드를 파싱해야 하는데, 이럴 때 사용할 수 있다.[6] 자연어도 기본적으로는 문맥자유 언어로 볼 수 있기 때문에 생성언어학에서도 문법을 분석할 때 사용한다.
3.3. 튜링 기계
튜링 기계\[Turing machine]는 내부 상태 외의 저장 공간으로 무한한 크기의 1차원 테이프를 갖는 오토마타이다. 이제는 입력 문자열도 테이프 위에 주어지며, 이를 순서대로 읽을 필요도, 모두 읽을 필요도 없다. 현재 헤드가 가리키는 칸의 글자를 읽고, 읽은 글자와 내부 상태에 따라 현재 위치에 필요한 글자를 쓰고 헤드를 왼쪽 또는 오른쪽으로 1칸 옮긴 후 내부 상태를 바꾸면서 동작한다. 이 과정을 정지 상태에 도달할 때까지 반복한다. 만약 언젠가는 정지 상태에 도달한다면 주어진 문자열을 받아들이고, 정지 상태에 영원히 도달하지 않는다면 주어진 문자열을 받아들이지 않는다.튜링 기계에는 여러 변형과 확장형이 있다. 변형으로는 1차원 테이프가 한쪽으로만 무한한 경우[7], 헤드를 1칸 옮기는 것 외에 움직이지 않는 것도 가능한 경우 등이 있다. 이런 경우 모두 원래 튜링 기계와 동일한 계산능력을 가진다. 확장형으로는 1차원 테이프를 여러 개 가지는 튜링 기계도 있고, 헤드가 여러 개인 경우 등이 있는데, 이 경우도 모두 원래 튜링 기계와 동일한 계산능력을 가진다. 심지어 비결정적 튜링 기계도 결정적 튜링 기계와 계산능력이 동일하다.
튜링 기계가 받아들이는 언어의 집합은 무제한 문법\[unrestricted grammar]에서 생성할 수 있는 재귀적 열거가능 언어\[recursively enumerable language]의 집합과 같다. 언어 [math(L _4 = \left \{ 0 ^n 1 ^n 0^n | n \in \N _0 \right \})][8]는 재귀적 열거가능 언어의 예시 중 하나이다. 심지어 '튜링 기계 하나와 이 튜링 기계가 받아들이는 문자열 하나'의 집합도 재귀적 열거가능 언어이다. 튜링 기계로 튜링 기계를 작동할 수 있다는 뜻이며, 이렇게 튜링 기계 하나와 문자열 하나를 입력받아 그 결과를 계산하는 튜링 기계를 보편 튜링 기계\[universal Turing machine]라 한다.
만약 어떤 언어 [math(L)]에 대해, 정지 상태가 [math(0)], [math(1)]뿐이고 입력으로 [math(L)] 내의 문자열이 들어오면 [math(1)]에서 정지, 그 외의 문자열이 들어오면 [math(0)]에서 정지하는 튜링 기계 [math(M)]이 존재한다고 하면, [math(M)]은 [math(L)]을 결정한다고 하고, 이런 튜링 기계가 존재하는 언어를 재귀언어\[recursive language]라고 한다. 위의 [math(L _4)]는 재귀언어의 예시 중 하나이고, 재귀언어의 집합은 재귀적 열거 가능 언어의 집합의 진부분집합이다.
재귀언어의 집합은 튜링 기계가 풀 수 있는 문제의 집합으로도 생각할 수 있는데, 유한 시간 내에 해당 문자열이 어떤 언어에 속하는지를 알려주는 튜링 기계가 존재하기 때문이다.[9] 튜링 기계는 기계적으로 계산가능한 모든 문제를 풀 수 있다고 추측된다. 이것을 처치·튜링 명제\[Church–Turing thesis]라 하며, 몇몇 학자들은 이를 가지고 알고리즘을 주어진 입력에 대해 올바른 출력을 하고 정지하는 튜링 기계로 정의하기도 한다.
튜링 기계로 계산불가능한 문제도 당연히 존재하며, 대표적인 예시로는 정지 문제가 있다. 정지 문제는 "주어진 튜링 기계에 주어진 문자열을 입력하고 작동시킨다면 언젠간 정지하는가?"인데, 앨런 튜링이 이 문제를 튜링 기계로 풀 수 없음을 증명했다. 다른 계산불가능한 문제는 보통 이 정지 문제를 해당 문제로 바꿔서 증명한다.
현대 컴퓨터는 튜링 기계를 기반으로 하기 때문에 컴퓨터가 풀 수 있는 문제는 모두 튜링 기계로 풀 수 있다.[10] 반대로 어떤 기계가 튜링 기계가 풀 수 있는 모든 문제를 풀 수 있다면, 해당 기계를 튜링 완전하다고 한다. 현실의 컴퓨터는 저장 공간이 유한하므로 튜링 완전할 수 없는데, 이처럼 다른 조건은 충족하지만 저장 공간만 유한한 경우에는 느슨하게 튜링 완전하다고 한다.
3.3.1. 선형 유계 오토마타
선형 유계 오토마타\[linear bounded automaton]는 튜링 기계의 제한형으로, 사용할 수 있는 테이프의 길이가 주어진 입력의 길이의 선형 함수로 제한된 튜링 기계이다. 또는, 입력 문자열이 적힌 칸과 끝을 표시하는 양쪽 한 칸씩만을 사용할 수 있다는 더 강한 조건으로 제한하는 경우도 있는데, 둘 중 어떤 조건으로 오토마타를 만들어도 같은 계산능력을 가진다.비결정적 선형 유계 오토마타가 받아들이는 언어의 집합은 문맥민감 문법\[context-sensitive grammar]에서 생성할 수 있는 문맥민감 언어\[context-sensitive language]의 집합과 같다. 위 문단에서 본 예시인 [math(L _4 = \left \{ 0 ^n 1 ^n 0^n | n \in \N _0 \right \})]는 문맥민감 언어의 예시이기도 하다. 결정적 선형 유계 오토마타와 비결정적 선형 유계 오토마타의 계산능력이 동일한지는 아직 밝혀지지 않았다.
선형 유계 오토마타는 저장 공간을 제한함으로써 현실적인 컴퓨터의 모델로서 튜링 기계보다 더 적합하다.
3.4. 기타
이 외에도 다양한 오토마타가 존재한다. 예를 들어, 저장 공간으로 큐를 갖는 오토마타도 생각할 수 있으며, 푸시다운 오토마타의 확장형으로 저장 공간으로 스택을 2개 가지는 오토마타[11]도 생각할 수 있다. 동작이 확률적인 오토마타나 양자적인 오토마타도 많이 연구되고 있다.3.5. 세포 자동자
세포 자동자\[cellular automata]는 일정한 형태로 놓인 세포들이 각 단위시간마다 주변 세포의 상태에 따라 자신의 상태를 바꾸며 동작하는 특수한 형태의 오토마타이다. 위에서 본 오토마타와 많이 달라 보이는데, 각 세포를 주변 세포의 상태를 입력으로 받는 유한 상태 기계라고 생각하면 이해하기 쉬울지도 모르겠다.이러한 개념은 요한 폰 노이만이 처음으로 제시했으며, 폰 노이만은 이를 가지고 DNA 같은 자가복제 구조를 연구해 이러한 구조를 제시했다.[12] 폰 노이만의 세포 자동자는 각 세포가 격자형으로 배열되어 29가지의 상태 중 하나를 가질 수 있으며, 인접한 4개의 세포의 상태에 따라 상태가 바뀌는 구조이다.
이 개념은 콘웨이의 생명 게임 때문에 널리 알려졌다. 콘웨이는 이 세포 자동자로 여러 흥미로운 구조와 더 간단한 자가복제 구조를 만들어 냈다. 실제 예시는 해당 문서 참조.
이 외에도 1차원의 경우, 세포가 육각형으로 배열된 경우 등 여러 세포 자동자가 연구됐다. 이 개념은 생물학이나 물리학 등 여러 분야에서 응용되고 있다.
[1]
'[math(|)]'는 '또는'을 의미하며, 좌변이 같은 생성 규칙을 한 줄에 적을 때 사용한다. 예를 들어 "(주격 조사) [math(\rightarrow)] 이 [math(|)] 가"는 생성규칙 "(주격 조사) [math(\rightarrow)] 이"와 "(주격 조사) [math(\rightarrow)] 가"를 한 번에 나타낸다.
[2]
생성 규칙이 적용된 부분을 진하게 표시했다.
[3]
여기서 지수 표현은 문자열이 나열된 개수를 의미한다. [math(0 ^n)]은 [math(0)]이 [math(n)]번 나열된 문자열을 뜻하며, 따라서 [math(L _1)]은 [math(0)]만으로 이루어진 문자열의 집합이다.
[4]
같은 개수의 [math(0)]과 [math(1)]이 [math(0 \cdots 01 \cdots 1)] 꼴로 나열된 문자열의 집합이다.
[5]
[math(\Sigma ^*)]은 알파벳 [math(\Sigma)]로 만들 수 있는 모든 문자열의 집합을, [math(w ^\mathrm {T})]는 문자열 [math(w)]를 뒤집어서 만든 문자열을 나타낸다. 따라서 [math(L _3)]은
회문의 집합이다.
[6]
다만 일반적인 문맥자유 언어의 파싱은 시간복잡도가 [math(O \left ( n ^3 \right ))]이라, 실제로는 프로그래밍 언어를 문맥자유 문법에서 제한사항을 더 둔 LL문법이나 LR, SLR, LALR 문법을 가지고 만들어 선형 시간 내에 파싱할 수 있도록 한다.
[7]
이 경우 가장 첫 칸은 고정적으로 공백이어야 한다.
[8]
[math(1)]만으로 구성된 문자열 양쪽에 각각 [math(1)]과 같은 개수의 [math(0)]이 나열된 문자열의 집합이다.
[9]
재귀언어가 아닌 재귀적 열거가능 언어의 경우, 속하지 않는 문자열에 대해 튜링 기계가 정지하지 않는다.
[10]
단, 시간의 관점에서는 다를 수 있는데, 현대 컴퓨터는 정확히는 튜링 기계와 동치인 임의접근 기계\[random-access machine\]를 기반으로 하기 때문이다. 그렇다고 현대 컴퓨터에서 다항 시간 내에 풀 수 있는 문제를 튜링 기계에서 다항 시간 내에 못 푸는 경우는 없지만, 세부적으로는 튜링 기계가 더 느릴 수 있다. 예를 들어, 정렬된 자료에서의 탐색은 현대 컴퓨터에서는 [math(O \left ( \log n \right ))]이 걸리지만, 튜링 기계에서는 [math(O \left ( n \right ))]이 걸린다.
[11]
이 오토마타는 튜링 완전하다.
[12]
당시는 유전자 복제 메커니즘이 발견되기 수십 년 전이었다.