둘 다 유한 오토마타이고, 알아볼 수 있는 언어도 똑같이 정규 언어다. 가르는 질문은 “한 상태에서 글자 하나를 읽었을 때 갈 곳이 하나로 정해지는가”다. 정해지면 DFA(결정적 유한 오토마타), 여러 곳이 될 수 있거나 글자 없이도 옮길 수 있으면 NFA(비결정적 유한 오토마타)다. 갈림길이 없는 외길과, 갈림길마다 분신을 보내 모든 길을 한꺼번에 가 보는 미로의 차이다. 분신 비유는 “한꺼번에”까지만 맞다. 실제 컴퓨터는 분신을 못 만들어서 길을 하나씩 가 보거나 분신들이 있는 칸의 모음을 들고 다닌다.
같은 언어, 두 기계
\(\Sigma = \{0, 1\}\)에서 “00으로 끝나는 줄”, 곧 \((0 \mid 1)^*00\)을 알아보는 두 기계다.
flowchart LR
S["시작"] --> q0(("q0"))
q0 -->|"1"| q0
q0 -->|"0"| q1(("q1"))
q1 -->|"0"| q2((("q2")))
q1 -->|"1"| q0
q2 -->|"0"| q2
q2 -->|"1"| q0
DFA다. 상태마다 0과 1의 화살표가 하나씩 있다. q0은 “방금 0을 못 봤다”, q1은 “끝이 0 하나”, q2는 “끝이 00”이다1.
flowchart LR
S["시작"] --> q0(("q0"))
q0 -->|"0, 1"| q0
q0 -->|"0"| q1(("q1"))
q1 -->|"0"| q2((("q2")))
NFA다. q0에서 0을 읽으면 q0에 머물 수도, q1로 갈 수도 있다. 정규 표현식의 모양 그대로다. q0의 고리가 \((0 \mid 1)^*\), 뒤의 두 화살표가 \(00\)이다.
100을 넣는다.
| 읽은 글자 | DFA의 상태 | NFA에서 말이 있을 수 있는 상태 |
|---|---|---|
| (처음) | q0 | q0 |
| 1 | q0 | q0 |
| 0 | q1 | q0, q1 |
| 0 | q2 | q0, q1, q2 |
DFA는 길이 하나다. q2에서 끝나 받아들인다. NFA는 끝까지 간 길이 셋이다(q0에 계속 머문 길, 마지막에 q1로 간 길, q1을 거쳐 q2로 간 길). 그 가운데 하나가 q2에서 끝나므로 받아들인다1.
어느 쪽일까
C1 (a) 정규 표현식을 보고 손으로 오토마타를 빨리 그려야 한다. (b) 수십만 줄짜리 원시 프로그램의 글자를 하나씩 읽으며 토큰을 잘라야 한다. 각각 DFA와 NFA 중 어느 쪽이 맞는가?
답: (a) NFA. 정규 표현식의 조각을 ε-화살표로 이어 붙이기만 하면 된다. (b) DFA. 글자 하나에 표 한 칸만 읽으면 다음 상태가 정해진다.
이유: NFA는 만들고 읽기 쉽지만 돌릴 때 여러 길을 따져야 해서 느리다. DFA는 돌릴 때 빠르지만 손으로 만들기 어렵고 상태가 많아질 수 있다. 그래서 어휘 분석기는 NFA로 만든 뒤 DFA로 바꿔서 쓴다.
C2 위의 두 기계에 1001을 넣는다. DFA가 거치는 상태를 차례로 쓰고, NFA에서 끝까지 간 길과 중간에 막힌 길이 각각 몇 개인지 쓰라. 두 기계의 답은 같은가?
답: DFA는 q0 → q0 → q1 → q2 → q0. q0에서 끝나 거절한다. NFA에서 끝까지 간 길은 q0에만 머문 하나이고, 중간에 막힌 길이 둘이다(q1에서 1을 만난 길, q2에서 1을 만난 길). 받아들이는 상태에서 끝난 길이 없어 거절한다. 답이 같다.
이유: NFA의 q1과 q2에는 1로 나가는 화살표가 없다. 막힌 길은 버린다. 길이 하나라도 받아들이는 상태에서 끝나야 받아들이는데 그런 길이 없다.
결정적 차이
| DFA | NFA | |
|---|---|---|
| 한 상태에서 한 글자로 가는 전이의 수 | 0개 또는 1개 | 0개 이상 |
| ε-전이 | 없다 | 있어도 된다 |
| 입력 하나에 대한 길의 수 | 많아야 하나. 갈라지지 않는다 | 0개 이상. 여럿일 수 있다 |
| 받아들이는 조건 | 그 길이 받아들이는 상태에서 끝난다 | 받아들이는 상태에서 끝나는 길이 하나라도 있다 |
| 장점 | 돌릴 때 빠르다(길이 하나) | 적기 쉽다(만들기도 읽기도 쉽다) |
| 단점 | 복잡하다. 자리를 많이 쓴다(NFA보다 지수적으로 커질 수 있다) | 느리다(길이 여럿) |
DFA라도 끝까지 가는 길이 늘 하나 있는 것은 아니다. 표에 빈 칸이 있으면 길이 중간에 끊긴다. \(1^*0\)의 DFA(\(q_0\)에서 1이면 \(q_0\), 0이면 \(q_1\))에 01을 넣으면 둘째 글자에서 갈 곳이 없어 끝까지 가는 길이 0개다. NFA도 모든 길이 중간에 막힐 수 있다. 그래서 DFA를 가르는 것은 “길이 하나다”가 아니라 “길이 갈라지지 않는다”이다2.
선택을 가르는 줄은 장점과 단점이다. 돌리는 속도가 중요하면 DFA, 만드는 쉬움이 중요하면 NFA다. 알아볼 수 있는 언어는 같아서 “어느 쪽이 더 많은 것을 알아보는가”는 선택 기준이 아니다. NFA를 같은 언어의 DFA로 바꾸는 방법이 부분집합 구성법이고, 그 문서에서 상태 \(n\)개짜리 NFA가 \(2^n\)개짜리 DFA가 되는 예를 본다.
100의 추적, 빈 칸이 있는 DFA에서 길이 끊기는 예, 카드 C2의 길 수 — 07_dfa-vs-nfa_verify.py