유한 오토마타는 유한한 개수의 상태만으로 문자열을 인식하는 기계이고, 정규표현이 나타내는 언어와 정확히 같은 범위를 인식한다. DFA와 NFA는 그 두 가지 형태로, 표현력은 같지만 실행 비용과 만들기 쉬운 정도가 다르다.
렉서 생성기가 정규표현을 받아 스캐너를 뱉는 과정이 결국 이 둘 사이의 변환이다.
정규표현 → ε-NFA → DFA → 최소화된 DFA 만들기 쉽다 실행이 싸다 표가 작다유한 오토마타
Section titled “유한 오토마타”형식적으로는 다섯 개의 구성원소로 정의한다.
M = (Q, Σ, δ, q₀, F)
Q : 상태들의 유한집합Σ : 입력기호들의 유한집합δ : 상태전이함수q₀ : 시작상태, q₀ ∈ QF : 종료상태들의 집합, F ⊆ Q식별자(첫 글자는 영문자, 이후는 영문자나 숫자)를 인식하는 오토마타라면 이렇게 된다.
Q = {q₀, q₁}, F = {q₁}
δ │ 영문자 │ 숫자 ─────┼────────┼────── q₀ │ q₁ │ ― q₁ │ q₁ │ q₁abc를 넣으면 q₀ -a→ q₁ -b→ q₁ -c→ q₁이고, 끝난 자리가 종료상태이므로 받아들인다. 렉서가 하는 일이 정확히 이것이다.
DFA와 NFA의 구분은 전이함수 δ의 모양 하나에서 온다.
| DFA | NFA | |
|---|---|---|
| 전이함수 | δ : Q × Σ → Q | δ : Q × Σ → 2^Q |
| 한 입력에 대한 다음 상태 | 정확히 하나 | 0개 이상 |
| ε 전이 | 없다 | 있을 수 있다 |
DFA는 매 순간 어디에 있는지가 하나로 정해진다. NFA는 여러 곳에 동시에 있을 수 있고, 입력을 읽지 않고도 상태를 옮기는 ε 전이를 가질 수 있다.
0이 연속 두 개거나 1이 연속 두 개인 문자열을 받아들이는 NFA다.
Q = {q₀, q₁, q₂, q₃, q₄}, F = {q₂, q₄}
δ │ 0 │ 1 ─────┼────────────┼──────────── q₀ │ {q₀, q₃} │ {q₀, q₁} q₁ │ ― │ {q₂} q₂ │ {q₂} │ {q₂} q₃ │ {q₄} │ ― q₄ │ {q₄} │ {q₄}q₀에서 0을 보면 q₀에 머무를 수도, q₃로 갈 수도 있다. “여기서부터 00이 시작될지도 모른다”는 추측을 분기로 표현한 것이다. 01001을 넣으면 도달 가능한 상태가 {q₀, q₁, q₄}가 되고, 종료상태 q₄를 포함하므로 받아들인다. NFA는 갈 수 있는 모든 상태의 집합을 동시에 들고 다니므로, 하나만 종료상태에 걸리면 인식이다.
NFA는 언어의 구조를 그대로 옮기기 쉽다. “00이 있거나 11이 있다”를 두 갈래로 나눠 그리면 끝이다. 반면 이걸 DFA로 직접 그리려면 “지금까지 무엇을 봤는지”를 상태에 전부 인코딩해야 해서 훨씬 어렵다.
DFA는 실행이 싸다. 상태 하나와 입력 하나로 다음 상태가 배열 조회 한 번에 나온다. NFA는 상태 집합을 유지하며 매 글자마다 집합 전체를 갱신해야 한다. 그래서 만들기 쉬운 쪽으로 만들고 실행이 싼 쪽으로 바꾼다. 이 변환이 가능한 이유는 둘이 동치이기 때문이다. DFA는 NFA의 특수한 경우이므로 한쪽은 자명하고, 반대 방향이 부분집합 구성이다.
프로그래밍 언어가 “정규식”이라고 부르는 것은 여기서 말하는 정규표현이 아니다. 역참조나 전방탐색이 붙는 순간 정규언어를 벗어나고, DFA로 변환할 수 없게 된다. 그래서 대부분의 정규식 엔진은 DFA 대신 NFA를 백트래킹으로 흉내 내고, 그 결과 (a+)+$ 같은 패턴에서 입력 길이에 지수적인 시간이 걸린다. ReDoS가 이 성질을 이용한 공격이다. DFA로 변환해 쓰는 도구(flex, RE2)에는 이 문제가 없는 대신 역참조를 지원하지 않는다.
정규표현에서 DFA로
Section titled “정규표현에서 DFA로”Thompson 구성은 정규표현의 각 연산자에 대응하는 조각을 만들어 이어 붙인다.
ε → ──ε──▶◎
a → ──a──▶◎
N₁ | N₂ → ε로 갈라져 N₁과 N₂로 들어갔다가 ε로 다시 합류
N₁ N₂ → N₁의 종료상태를 N₂의 시작상태에 ε로 연결
N* → N을 감싸고, 시작→종료 ε(0회)과 종료→시작 ε(반복)을 추가조각마다 상태를 상수 개만 쓰므로 NFA의 상태 수가 정규표현 길이에 선형이다. ε 전이를 자유롭게 쓸 수 있어서 조각을 아무렇게나 이어 붙여도 되고, 이것이 NFA를 경유하는 이유다.
거꾸로 NFA를 DFA로 바꾸는 것이 부분집합 구성이다. DFA의 상태 하나를 NFA 상태들의 집합으로 잡는다. NFA가 “동시에 여러 곳에 있다”면, 그 “여러 곳”을 통째로 하나의 이름으로 부르면 결정적이 된다.
ε 전이를 흡수하기 위해 ε-closure를 정의한다.
ε-closure(S) = S와, S에서 ε 지시선만 따라 도달할 수 있는 모든 상태의 집합 (더 이상 변하지 않을 때까지 반복)ε-closure(T) = ⋃ ε-closure(x) (x ∈ T)변환 절차는 이렇다.
ε-closure(q₀)를 DFA의 시작상태로 놓는다- 현재 상태 집합에서 ε을 제외한 각 입력기호로 갈 수 있는 상태들을 모아 다시 ε-closure를 취한다. 이미 만든 집합과 같으면 새 상태를 만들지 않고 지시선만 잇는다
- 새 상태가 나오지 않을 때까지 반복한다. NFA의 종료상태를 하나라도 포함하는 집합은 전부 DFA의 종료상태다
(a|b)*abb를 인식하는 ε-NFA(상태 0~10, 종료 10)에 적용해 보면 이렇게 시작한다.
A = ε-closure(0) = {0, 1, 2, 4, 7, 8} ← 시작상태
A에서 a → {3, 9} B = ε-closure(3, 9) = {1, 2, 3, 4, 6, 7, 8, 9, 10}A에서 b → {5} C = ε-closure(5) = {1, 2, 4, 5, 6, 7, 8}이어서 B, C에 같은 일을 반복하면 상태가 A~E 다섯 개에서 멈춘다.
δ │ a │ b ───┼─────┼───── A │ B │ C B │ B │ D C │ B │ C D │ B │ E E │ B │ C F = {E}만들어진 DFA의 상태 이름이 NFA 상태들의 집합이다. 이론적으로는 NFA 상태가 n개면 부분집합이 2ⁿ개이므로 DFA 상태가 지수적으로 불어날 수 있다. 실제 프로그래밍 언어의 토큰 규칙에서는 그런 경우가 거의 없지만, 기계 생성된 거대한 정규표현에서는 실제로 터질 수 있다.
부분집합 구성으로 나온 DFA에는 보통 군더더기가 있다. 위 표에서 A, C, E는 a로도 b로도 완전히 같은 곳으로 간다.
두 상태를 구별할 수 있다는 것은, 같은 문자열 w를 각각에서 읽었을 때 한쪽만 종료상태에 도달하는 w가 존재한다는 뜻이다. 그런 w가 없으면 두 상태는 합쳐도 된다.
절차는 분할을 계속 쪼개 나가는 것이다.
- 도달 불가능한 상태를 제거한다
- 종료상태와 비종료상태, 두 동치류로 나눈다
- 같은 입력기호에 대해 서로 다른 동치류로 가는 상태가 한 동치류 안에 있으면 그 동치류를 쪼갠다
- 더 이상 쪼개지지 않을 때까지 반복한다
위 DFA에 적용하면 이렇게 진행된다.
초기 {A, B, C, D} | {E}b로 분할 D는 E(2번류)로 가고 나머지는 1번류로 간다 {A, B, C} | {D} | {E}b로 분할 B는 D로, A와 C는 C로 간다 {A, C} | {B} | {D} | {E}더 이상 쪼개지지 않음{A,C}, {B}, {D}, {E}를 각각 X, Y, Z, W로 두면 상태가 다섯 개에서 네 개로 줄어든다.
δ' │ a │ b ───┼─────┼───── X │ Y │ X Y │ Y │ Z Z │ Y │ W W │ Y │ X F' = {W}babb를 넣으면 X -b→ X -a→ Y -b→ Z -b→ W로 종료상태에 도달한다. (a|b)*abb가 맞다.
이 최소화가 실무에서 의미가 있는 이유는 상태 수가 곧 전이표의 세로 길이이기 때문이다. 표 크기는 상태 수 × 입력기호 수이고, 렉서는 이 표를 메모리에 상주시킨다.
flex가 하는 일이 위 파이프라인 그대로다. 규칙마다 정규표현을 NFA로 만들고, 전부 합쳐 하나의 NFA로 만든 뒤, 부분집합 구성으로 DFA를 만들고 최소화한다. 다만 규칙이 여러 개이므로 종료상태에 “몇 번 규칙으로 accept인가”를 함께 기록한다. 생성된 코드의 yy_accept[]가 그 배열이다.
표의 가로 폭을 줄이는 수단도 하나 더 붙는다. 같은 문법 안에서 완전히 똑같이 취급되는 문자들을 하나의 등가 클래스로 묶으면, 상태 수 × 256이 상태 수 × 클래스 수가 된다. 상태 최소화가 세로를 줄이고 등가 클래스가 가로를 줄인다.
여기까지가 상태만으로 되는 일이다. 상태가 유한하므로 중첩 괄호의 깊이 같은 것은 기억할 수 없고, (ⁿ)ⁿ을 인식하려면 스택이 필요하다. 그것이 푸시다운 오토마타이자 문맥 자유 문법이다. 렉서와 파서가 나뉘는 경계가 정확히 여기이고, 그 계층 전체는 오토마타 계층에 정리했다.
참고