오토마타 (Automata), 그게 대체 뭔데?

시작하기 전에...

먼저 형식 언어에 대해 어느 정도 알고 계셔야 합니다.

형식 언어 (Formal Language)

---

오토마타가 뭘까?

오토마타 (Automata)는 계산 (Computation)을 묘사하는 수학적 모델입니다.

컴퓨터는 우리가 내린 지시를 따릅니다. 복잡한 지시들도 사실은 굉장히 간단한 지시들이 여러 개 모여서 가능하게 됩니다. 이 간단한 지시가 뭘까요? 특정한 명령을 따를 수 있는 능력이 있으면 모든 알고리즘을 묘사할 수 있을까요?

예를 들어 가장 간단한 오토마타는 DFA (Deterministic Finite Automata)입니다. DFA에는 5가지 요소가 있습니다.

1. Q: 가능한 모든 상태
2. Σ: Input으로 받을 수 있는 알파벳
3. δ: 현재 상태와 Input을 받고 새로운 상태를 뱉어내는 함수
4. q0: 초기 상태
5. F: 가능한 모든 상태의 부분집합

여기서 특정 상태에서 어떤 상태를 뱉을지가 미리 다 정해져 있고, DFA는 Input을 처음부터 끝까지 읽으면서 상태를 바꿔 갑니다. 그리고 최종적인 상태가 F에 있으면 true이고, 없으면 false입니다.

예를 들어 이진수 (0/1로 이루어진 숫자)를 받아서 이 숫자가 10보다 큰지 판명하는 DFA를 만든다고 해 보겠습니다. 우선 요소 5개를 정의하겠습니다.

1. Q = {q0, q1, q2, q3, q4, q5, qx}
2. Σ = {0, 1}
3. δ: 아래에서 정의
4. q0: q0
5. F = {q5}

 

🐜 상태

q0	시작점
q1	1을 읽었음
q2	10
q3	101
q4	숫자가 10보다 큼
qx	숫자가 10보다 작거나 이상한 숫자

 

🐜 상태 변화 함수 (δ)

숫자는 왼쪽부터 읽는다고 가정하겠습니다. 그리고 간단함을 위해 무조건 4개의 숫자를 줘야 하고, 0으로 시작할 수는 없다고 가정하겠습니다.

현재 상태	Input	변경될 상태	설명
q0	0	qx	이진수면 1로 시작해야 하는데 0으로 시작하면 안 되니깐 바로 종료
q0	1	q1	-
q1	0	q2	여태까지 10 이니깐 계속 진행해야 함
q1	1	q4	숫자가 무조건 4개 있는데 시작이 11이니깐 나머지가 00이여도 1100 = 12이기 때문에 무조건 10보다 큼
q2	0	q2	여태까지 100인데 마지막이 1이더라도 1001 = 9니깐 10보다 작아서 종료
q2	1	q3	여태까지 101인데 마지막이 0이면 1010 = 10이여서 10보다 크지 않고, 마지막이 1이면 1011이라 10보다 크기 때문에 계속 확인해야 함
q3	0	qx	1010 = 10이니깐 10보다 크지 않음
q3	1	q4	1011 = 11이니깐 10보다 큼
q4	0/1	q5	한 번 10보다 크다고 판명 났으면 숫자가 아무리 길어져도 10보다 커지기만 함
qx	0/1	qx	한 번 끝났으면 끝난채로 유지

 

이걸로 DFA로 "10보다 큰 숫자를 판명"하는 계산을 할 수 있다는게 증명 됐습니다. DFA를 다루면 몇 가지 특징이 보입니다.

• DFA는 장기 기억이 없습니다. 지금 상태만 알 수 있고, 이를 바탕으로 미리 정해진대로 다음 상태를 바꾸는 계산만 할 수 있습니다.
• 규칙이 한 번 정해지면 바꿀 수 없습니다.

이런 상황에서 DFA가 풀 수 없는 문제가 있을까요? 있습니다! 바로 괄호가 올바르게 돼 있는지 판명하는 문제입니다. 괄호가 올바르게 돼 있는지 판명하기 위해서는 여태까지 나왔던 모든 여는 괄호의 개수를 기억하고, 닫는 괄호가 나올 때마다 그 개수를 줄여야 합니다. 괄호의 개수는 임의로 정해지기 때문에 상태로 표현할 수 없습니다. 

코딩 테스트에서는 보통 Stack이라는 데이터 구조를 사용해서 푸는데, DFA는 Stack을 구현할 수 없습니다.

프로그래머스

 

이걸로 계산 능력에는 종류가 있고, 어떤 계산 능력은 다른 계산 능력보다 뛰어나다는 걸 알게 됐습니다. 오토마타가 바로 여러 계산 능력을 분류하고 연구하기 위해 생겨난 모델입니다.

 

---

 

형식 언어와 오토마타

이런 계산 과정을 묘사하기 위해서는 명확한 언어로 전달을 해 줘야 합니다. 위에서 10보다 큰 숫자를 판명하기 위해 쓴 언어는 수학의 언어 (집합론) 입니다. 수학, 프로그래밍 언어 등 알고리즘을 애매함 없이 명확하게 묘사하기 위해 쓰는 언어를 형식 언어 (Formal Language)라고 합니다. 

형식 언어는 특정 능력을 계속 추가하면서 여러 종류를 만들 수 있습니다. 그리고 오토마타는 이 형식 언어가 묘사하는 계산 (Computation)을 할 수 있을 수도 있고, 없을 수도 있습니다. 가장 약한 형식 언어 (Subregular Language)와 가장 강력한 형식 언어 (Recursively Enumerable Languages)는 있지만, 그 사이에는 여러 능력을 추가하면서 거의 무한에 가까운 형식 언어를 만들 수 있습니다. 당연히 이 모든 형식 언어를 공부할 필요도 없고, 이 모든 형식 언어에 딱 맞는 오토마타가 있을 리도 없습니다.

 

형식 언어	계산할 수 있는 오토마타
Regular Language	DFA, NFA, ε-NFA
Context-Free Language	PDA
Deterministic CFL	NPDA
Context-Sensitive Language	LBA
Recursively Enumerable Language	Turing Machine

---

오토마타의 종류

FA	Finite Automaton	현재 상태를 기반으로 읽으면서 정해진 규칙대로 상태를 바꿀 수 있음
DFA	Deterministic Finite Automaton	다음 상태가 무조건 1개로 정해져 있음
NFA	Non-deterministic Finite Automaton	다음 상태가 여러개 있을 수 있고, 없을 수 있고, 상태 변화 없이 넘어갈 수도 있음
PDA	Push-Down Automaton	Stack을 쓸 수 있음
NPDA	Non-determinisitc Push-Down Automaton	Stack을 쓸 수 있으면서 다음 상태가 1개로 정해져 있지 않음
LBA	Linear-Bounded Automaton	Turing Machine인데 메모리 크기가 Input 크기 만큼 밖에 없음
TM	Turing Machine	Input을 변경할 수 있고, 좌우로 움직일 수도 있고, Stack을 쓸 수도 있음

 

🐜 상태가 정해져 있지 않으면 왜 강력해 질까?

사실 상태가 정해져 있지 않다고 더 강력해 지는 건 아닙니다.  하지만 PDA/NPDA의 경우에는 Nondeterministic 덕분에 동시 분기가 가능해 NPDA가 Stack을 1개만 가질 때는 할 수 없는 일부 동작이 가능해 더 강력해집니다. 하지만 모델이 아닌 실제 컴퓨터는 무조건 Deterministic 하게 동작하기 때문에 실제로 이런 효과를 누릴 수는 없습니다.

 

🐜 스택이 뭐가 그렇게 중요할까?

사실 메모리를 가질 수 있다고 하면 배열 (Array)를 쓰면 됩니다. 왜 굳이 Stack을 사용할 수 있다고 했을까요? 사실 생각해 보면 Stack은 배열의 능력에 제한을 가한 겁니다. 배열보다 약하다고 볼 수 있습니다. 오토마타는 최약으로 시작해서 점점 능력을 주어 주면서 뭐가 가능한지 연구하는게 핵심입니다. 배열이 스택보다 강하니 당연히 더 약한 Stack을 주고 최소한으로 어디까지 할 수 있는지 보고, 그다음에 점점 강력한 도구를 주는 겁니다. 실제로 FA에서 배열을 사용 가능하게 하면 그냥 TM이 돼 버립니다.

 

🐜 TM이 가장 강력한 Automaton이라는걸 어떻게 알 수 있을까?

사실 정확히는 모릅니다. 처리-튜링 논제가 모든 알고리즘은 튜링 기계가 계산할 수 있다는 추측인데, 아직 증명되진 않았습니다. 하지만 여태까지 튜링 기계보다 강력한 오토마타가 발견된 적이 없고, 알려진 모든 컴퓨터 모델이 튜링 기계와 동일한 능력을 가졌기 때문에 튜링 기계가 가장 강력한 오토마타라고 추측하는 것뿐입니다. (나중에 더 강력한 오토마타가 발견될 수도 있습니다.)

---