From NFA to DFA, One Subset at a Time

Stage 2 에서 매 step 의 active 는 한 글자를 읽을 때마다 새로 계산되는 state 집합 이었습니다. 같은 집합이 두 번 나오면 그 다음 이동 역시 똑같을 수밖에 없습니다. 비결정성은 그 안에 담아두고, 바깥에서는 집합 자체를 한 덩어리처럼 다루자는 발상이 subset construction 입니다.

Stage 3 에서는 그 집합 하나를 DFA 의 state 하나로 승격합니다. 알파벳 Σ 를 한 바퀴 돌리면서 새 subset 이 나오면 queue 에 넣고, 이미 본 subset 이면 transition 만 잇고 넘어갑니다. 다 돌면 DFA 가 완성됩니다.

이번에는 뷰어가 좌우로 갈라집니다. 왼쪽에는 고정된 NFA 가 있고 step 마다 강조되는 subset 이 바뀝니다. 오른쪽은 그 subset 이 DFA 의 노드로 굳어지는 과정을 보여줍니다.

아래 뷰어의 slider 를 움직여 봅시다. (a|b)*c 의 NFA (왼쪽) 가 DFA state 네 개 (오른쪽) 로 접히는 열두 step 입니다.

처음 몇 step 에서는 오른쪽이 비어 있다가 초기 subset {0,2,4,6,7,8} 이 D0 으로 등장하고, a/b/c 에 대한 이동이 각각 D1/D2/D3 을 만들어냅니다. 그 다음 step 부터는 새 state 가 더 이상 생기지 않고 기존 subset 으로 되돌아오는 transition 만 추가됩니다. 열두 step 이 끝나면 DFA 노드 네 개와 transition 아홉 개로 마무리됩니다. 마지막 verdict step 에서 accept 는 {D3} 하나로 확정됩니다.

이 글은 Stage 3 을 세 commit 에 1:1 로 매핑합니다

Stage 2 는 뷰어를 재사용해서 커밋이 두 개였지만, Stage 3 은 DFA 전용 viz 가 필요해서 다시 세 커밋입니다 — 코드, artifact 재생성, viz 순서입니다. 섹션도 같은 순서로 이어갑니다.

Repo: github.com/Ricci-curvature/regex-viz

Stage 3 — Subset Construction

Commit: cbef387 — stage 03: subset construction (NFA → DFA trace)

src/dfa.rs 한 파일과 CLI 하나, 테스트 10 개가 핵심입니다. Stage 2 의 ε-closure 와 char_move 를 그대로 다시 씁니다 — 달라지는 것은 "입력 문자열을 한 글자씩 먹인다" 가 아니라 "알파벳 Σ 를 한 바퀴 돌려서 subset 이 어디로 가는지 본다" 는 점뿐입니다.

알고리즘 네 줄

Σ := NFA 의 non-ε label 을 모두 모아 정렬하고 dedup
D0 := ε-closure({ nfa.start })

worklist := [D0]
while worklist 비지 않음:
    cur := worklist.pop_front()
    for c in Σ:
        T := ε-closure( char_move(cur.subset, c) )
        T 가 공집합이면 continue
        T 가 처음 보는 subset 이면 새 DFA state 로 등록하고 worklist 에 push
        (cur --c--> T) transition 을 추가

핵심은 하나입니다. 비결정성은 "한 집합 안에 여러 state 가 공존한다" 는 형태로만 나타납니다. Stage 2 의 매 step 에 보였던 active 가 바로 그 집합이었고, Stage 3 에서는 그 집합 자체를 새 그래프의 노드 한 개로 올려 둡니다. 같은 subset 이 두 번 나오면 바깥에서 볼 때 구별할 수 없으니 하나의 DFA state 로 합칩니다.

왜 새 trace 타입을 따로 만들었나

Stage 1–2 에서 쓰던 Trace / Step 은 step 마다 NFA 스냅샷 하나를 실었습니다. 그 스냅샷은 start 와 accept 가 각각 하나씩 입니다. Thompson 의 구성 규칙이 그렇게 되어 있기 때문입니다.

그런데 subset construction 의 결과물은 다릅니다. 하나의 regex 에서 accept 가 여러 개 나올 수 있습니다. 예를 들어 a|b 를 DFA 로 접으면 D0 (초기) → D1 (a 를 읽고 도달) → D2 (b 를 읽고 도달) 가 되는데, D1 과 D2 가 둘 다 accept 입니다. 기존 Nfa 타입의 accept: usize 필드로는 표현할 수 없습니다.

게다가 viewer 는 두 개의 그래프 — 원본 NFA 와 자라나는 DFA — 를 동시에 보여줘야 합니다. 한 Step 안에 두 그래프를 억지로 넣으면 기존 포맷이 깨지고, Stage 1–2 의 artifact 가 전부 무효가 됩니다. 프로젝트 규칙상 포맷 변경은 breaking change 로 취급해 코드 커밋과 섞지 않으므로, 포맷을 건드리는 대신 별도 타입 (ConstructionTrace / ConstructionStep) 으로 분리했습니다.

src/dfa.rs 의 모양

전체는 300 줄 정도인데, 핵심 루프는 이 부분입니다.

let start_subset = sorted(&epsilon_closure(&nfa, [nfa.start]));
let start_id = add_state(&mut states, &nfa, start_subset.clone());
// ... "D0 등장" step emit
 
let mut queue: VecDeque<usize> = VecDeque::from([start_id]);
let mut processed: HashSet<usize> = HashSet::new();
 
while let Some(cur_id) = queue.pop_front() {
    if !processed.insert(cur_id) {
        continue;
    }
    let cur_subset: HashSet<usize> =
        states[cur_id].subset.iter().copied().collect();
 
    for &c in &alphabet {
        let moved = char_move(&nfa, &cur_subset, c);
        if moved.is_empty() {
            continue;
        }
        let target_set = epsilon_closure(&nfa, moved);
        let target_sorted = sorted(&target_set);
 
        let (target_id, is_new) = match find_state(&states, &target_sorted) {
            Some(id) => (id, false),
            None => {
                let id = add_state(&mut states, &nfa, target_sorted.clone());
                queue.push_back(id);
                (id, true)
            }
        };
 
        transitions.push(DfaTransition { from: cur_id, to: target_id, label: c });
        // ... step emit (is_new 에 따라 description 이 달라집니다)
    }
}

핵심은 BFS 워크리스트입니다. 재귀도, 백트래킹도 없고, 같은 subset 을 두 번 처리하지 않도록 processed 만 있으면 됩니다. find_state 는 선형 탐색으로 간단히 짰는데, Stage 3 크기의 regex 에서는 체감이 안 돼서 HashMap 인덱스는 붙이지 않았습니다.

Step 시퀀스의 구성

construction trace 는 매번 이 순서로 step 을 쌓아갑니다.

1. 알파벳 발표 — Σ = {a, b, c}. 아직 DFA state 는 없습니다.
2. 초기 state — D0 = ε-closure({start}). 오른쪽 pane 에 첫 노드가 등장합니다.
3. transition 추가 — 워크리스트에서 꺼낸 state 마다 Σ 를 훑으면서 이동합니다. 새 subset 이면 "new" description, 이미 본 subset 이면 "existing" description 으로 구분됩니다.
4. verdict — 전체 DFA state 수와 accept 집합을 한 줄로 찍습니다.

덕분에 slider 를 초기 쪽으로 되감으면 DFA 가 한 노드도 없는 상태에서 출발하고, 끝까지 가면 완성된 그래프가 남습니다. 글을 읽는 흐름과 알고리즘이 진행되는 흐름이 같은 축을 씁니다.

Stage 3 — Pinned Artifacts

Commit: 40ed64f — artifacts: regenerate stage03

여섯 개 regex 를 pin 으로 고정했습니다. 하나씩 열어보면서 DFA 가 어떻게 접히는지 확인해 봅시다.

a — 최소 사례

DFA state 는 둘뿐입니다. D0 = {0} 에서 a 를 읽으면 D1 = {1} 로 가고, D1 은 accept 입니다. NFA 와 DFA 가 거의 같은 모양인데, NFA 가 이미 결정적이면 DFA 도 같은 크기로 나올 수밖에 없기 때문입니다. 뒤의 예시는 모두 여기서 시작해 규모를 키워가는 흐름 입니다.

ab — concat 의 체인

주목할 점은 D1 = {1, 2} 입니다. NFA 에서 state 1 은 a 의 accept, state 2 는 b 의 start 인데, 둘은 concat ε-link 로 연결되어 있어서 ε-closure 를 씌우면 한 집합으로 묶입니다. 두 NFA state 가 DFA state 하나로 합쳐진다 는 개념이 여기서 처음 보입니다. 글자를 한 번 읽고도 subset 크기가 두 배가 되는 장면이기도 합니다.

a|b — accept 두 개

D0 에서 a 를 읽으면 D1 = {1, 5} 로, b 를 읽으면 D2 = {3, 5} 로 갑니다. 두 subset 모두 NFA 의 accept (state 5) 를 포함하므로 둘 다 accept 로 마킹 됩니다. 하나의 regex 가 DFA 에서는 여러 accept 를 가질 수 있다는 사실이 그림으로 드러나는 지점입니다. Stage 1–2 에서 쓰던 Trace 포맷이 이 stage 에서 부족한 이유도 같습니다 — 그쪽은 accept 를 한 개만 기록할 수 있으니 이 구조가 들어갈 자리가 없습니다.

a* — 초기 state 가 이미 accept

D0 = {0, 2, 3} 입니다. NFA 에서 state 3 은 accept 인데, star 의 bypass ε 덕분에 start (state 2) 에서 ε 만으로 이미 도달할 수 있습니다. 그래서 ε-closure 를 한 번 씌우자마자 accept 가 D0 에 같이 들어옵니다. 빈 문자열 매칭 = D0 이 accept 라는 사실이 Stage 2 에서는 "init 의 active 에 accept 가 이미 있다" 로 보였고, 여기서는 "D0 자체가 accept" 로 더 짧게 읽힙니다.

transition 쪽도 흥미롭습니다. D0 --a--> D1 을 따라가면 D1 = {0, 1, 3} 이 나오고, 그 다음 D1 --a--> D1 은 자기 자신으로 돌아오는 루프입니다. "한 번 a 를 읽었든 백 번을 읽었든 그 뒤에 갈 수 있는 state 는 같다" 는 점이 같은 subset 으로 드러납니다. slider 를 9 번째 step 근처로 옮기면 오른쪽 pane 에 두 번째 transition 이 새 노드를 추가하지 않고 기존 D1 에 되돌아가는 모습이 보입니다.

a+ — D0 은 accept 가 아닙니다

a* 와 모양이 거의 비슷하지만 한 군데에서 갈립니다 — D0 = {0} 은 accept 가 아닙니다. Plus 는 bypass ε 가 없어서 초기 집합에 NFA accept 가 끼어들 수 없습니다. "최소 한 번" 이라는 regex 의 의미가 D0 이 accept 에서 빠진 한 비트로 정확히 드러납니다. a 를 한 번 소비한 뒤에야 D1 = {0, 1, 2} 가 되고, 이후로는 a* 때와 같은 self-loop 가 이어집니다.

(a|b)*c — 루프 state 의 상호 이동

주 뷰어로 이미 본 regex 입니다. 이번에는 transition 하나하나를 따라가 봅시다.

• D0 = {0, 2, 4, 6, 7, 8} — 초기. (a|b)* 의 바깥 start, 두 branch 의 start, concat ε, 그리고 star bypass 로 도달하는 state 들이 모두 들어옵니다.
• D0 --a--> D1, D0 --b--> D2 — star 의 loopback ε 가 두 subset 을 다시 (a|b)* 내부로 되돌려 놓습니다. 그래서 D1 과 D2 는 NFA accept 를 포함하지 않습니다 (c 를 아직 안 읽었으니 accept 에 도달할 수 없습니다).
• D0 --c--> D3 = {9} — c 는 star 의 바깥으로 나가는 유일한 문자이고, state 9 는 accept 입니다. D3 이 유일한 accept 인 이유입니다.
• 이후 step 에서는 D1 과 D2 에 대해 같은 작업을 반복합니다. 흥미로운 지점은 D1 --a--> D1 (self-loop), D1 --b--> D2, D1 --c--> D3 세 이동이 모두 기존 subset 으로 되돌아온다 는 점입니다. 새 DFA state 는 더 생기지 않습니다.

"루프 안에 있는 동안은 D1 과 D2 사이를 왔다 갔다 할 뿐" 이라는 이 구조가 (a|b)*c 의 의미를 정확히 담고 있습니다. 끝은 c 여야 하고, 그 전까지는 a/b 를 몇 번이든 섞어 쓸 수 있다는 뜻입니다. 같은 성질이 Stage 2 에서는 "active 집합이 어떤 순간에도 동일하다" 로 보였는데, Stage 3 에서는 "D1 과 D2 두 state 사이를 돌 뿐" 이라는 더 작은 그림으로 요약됩니다.

pinning 의 의미

Stage 1–2 와 같습니다. 이 글의 뷰어들은 40ed64f 에 고정 되어 있어서, 이후에 subset construction 구현을 리팩터링하더라도 여기 보이는 step 수·description·subset 은 그대로 유지됩니다. Trace 포맷 자체 (ConstructionTrace) 가 바뀌면 stage03 전체를 regenerate 하고 이 포스트도 함께 업데이트합니다 — 코드 변경과 artifact regenerate 를 별개 커밋으로 쪼갠 이유도 이 원칙 때문입니다.

Stage 3 — Viewer

Commit: 382c24e — stage 03: viz components (ConstructionViewer + DfaGraph)

위 뷰어들은 전부 이 한 커밋의 산물입니다. 세 파일을 추가하고, 한 파일을 수정했습니다 (README).

viz/
├── construction.ts        ← src/dfa.rs 의 TypeScript mirror (~35 loc)
├── DfaGraph.tsx           ← DFA 전용 dagre + SVG (~160 loc)
└── ConstructionViewer.tsx ← 2-pane NFA + DFA + slider (~130 loc)

왜 TraceViewer 를 확장하지 않았나

Stage 2 때 TraceViewer 에 trace.kind === "run" 분기가 이미 들어 있었기 때문에, Stage 3 도 거기에 kind: "construction" 을 하나 더 추가해 확장하는 길이 있었습니다. 하지만 그 길은 택하지 않았습니다. 이유는 두 가지입니다.

1. payload 의 shape 이 근본적으로 다릅니다. Trace 는 "한 NFA, step 마다 active 만 바뀜" 입니다. ConstructionTrace 는 "두 개의 그래프 (NFA 는 고정, DFA 는 누적), step 마다 focus 가 양쪽에서 함께 움직임" 입니다. 한 컴포넌트로 합치면 매 render 마다 shape 분기가 트리 전체에 스며들어 코드가 "뭘 보여주려고 하는지" 흐려집니다.
2. 컴포넌트의 크기가 합리적 입니다. ConstructionViewer 는 130 줄이고, 그 안에서 NfaGraph 와 DfaGraph 를 조립합니다. 합치는 쪽을 "DRY" 라는 이유만으로 선택할 만큼 크지 않습니다.

대신 slider UX 는 그대로 가져왔습니다. step 인덱스, 이전/다음 버튼, description bar, 그리고 "step N / M" 카운터입니다. 독자가 Stage 1–2 에서 익힌 조작 감각이 그대로 통합니다. 달라지는 것은 위쪽 그림 영역이 두 pane grid 로 바뀌었다는 점뿐입니다.

DfaGraph 가 NfaGraph 와 다른 세 가지

• accept 가 여러 개 — 매 노드의 is_accept 플래그를 보고 accept 인 노드에 모두 double-circle 을 그립니다. NfaGraph 는 nfa.accept 하나만 비교하면 됐습니다.
• ε-edge 가 없음 — DFA 는 정의상 ε-transition 이 없습니다. 점선 스타일 분기와 ε label 처리가 모두 빠지면서 DfaGraph 쪽이 살짝 더 간결해집니다.
• 노드에 subset caption — D3 같은 라벨 아래에 {9} 처럼 NFA subset 을 같이 씁니다. 왼쪽 pane 에서 하이라이트되고 있는 NFA state 들이 어떤 DFA state 로 접힌 건지 바로 대응을 볼 수 있게 하려는 장치입니다. showSubset={false} props 로 끌 수도 있는데 기본값은 켜둔 상태입니다.

ConstructionViewer 의 grid

<div style={{ display: "grid", gridTemplateColumns: "1fr 1fr", gap: 12 }}>
  <Pane label="NFA (source)">
    <NfaGraph nfa={trace.nfa} active={step.focus_nfa_subset} />
  </Pane>
  <Pane label="DFA (under construction)">
    <DfaGraph
      states={step.dfa_states}
      transitions={step.dfa_transitions}
      focus={step.focus_dfa_state}
    />
  </Pane>
</div>

왼쪽의 active 자리에 focus_nfa_subset 을 그대로 넘기는 것이 결정적입니다. 매 step 의 "지금 다루고 있는 subset" 이 NFA pane 에서 노랗게 보이고, 동시에 그 subset 이 오른쪽 DFA pane 에서 어느 노드로 굳어지는지 focus_dfa_state 로 outline 됩니다. 두 pane 이 같은 step 객체를 서로 다른 각도에서 그리는 구조입니다.

DFA 의 첫 step 인 알파벳 발표에서는 오른쪽 pane 이 비어 있어야 합니다. 그런데 그 상태로 dagre 에 빈 그래프를 넘기면 0×0 SVG 가 나와서 UI 가 "컴포넌트가 깨졌나?" 로 읽히기 쉽습니다. DfaGraph 초반에 states.length === 0 이면 "(no DFA state yet)" 플레이스홀더를 그리는 분기를 넣었습니다.

Lessons

1. Trace 가 quadratic 으로 부풉니다. ConstructionStep 은 "그 순간까지의 누적 snapshot" 을 매 step 에 통째로 싣습니다. state 가 N 개까지 생긴 뒤에는 각 step 이 N 만큼의 state 를 반복 저장하게 되어, regex 크기가 커지면 JSON 이 O(N²) 로 커집니다. (a|b)*c 정도는 15KB 안팎이라 문제는 없지만, 알파벳이 크거나 DFA state 가 수백 개 나오는 regex 에서는 delta encoding 이 필요해질 겁니다. Stage 1–2 에서 미뤄둔 "delta 모드" 검토가 Stage 4 쯤 실제로 필요해질 것 같습니다.

2. find_state 가 선형 탐색입니다. "이 subset 이 이미 DFA state 로 등록되어 있는가" 를 매번 전체 states 를 훑어서 확인합니다. 알파벳을 |Σ|, state 수를 |D| 라고 하면 전체 construction 이 O(|Σ| · |D|²) 가 되어서, DFA 크기에 이차항이 붙습니다. subset 을 키로 하는 HashMap 하나만 붙이면 O(|Σ| · |D|) 로 내려가는데, 여섯 개 pin 에서는 체감이 안 돼서 일단 뒀습니다. Stage 4 에서 DFA simulation 을 붙일 때 DFA 자체를 크게 만들게 되면 그때 고칩니다.

3. 라벨이 char 이라 multi-char label 을 받지 못합니다. DfaTransition.label: char 로 잡아 두었기 때문에 Stage 5 쯤 character class ([a-z]) 나 escape sequence 를 도입하려 하면 구조 자체를 손봐야 합니다. compute_alphabet 안에 debug_assert!(chars.next().is_none(), …) 로 방어선을 하나 쳐둬서, 장래에 multi-char label 이 끼어들면 테스트 단계에서 잡힙니다. 포맷이 breaking 으로 넘어가는 지점은 이쪽일 것입니다.

다음 — Stage 4

DFA 가 생겼으니 두 갈래 중 하나를 골라야 합니다.

• 옵션 A: DFA simulator. 같은 regex 를 NFA (Stage 2) 와 DFA (Stage 4) 로 나란히 돌려서 step 수를 비교합니다. DFA 는 단일 state 만 들고 다니니 매 글자마다 O(1) 로 이동하고, "DFA 는 선형 시간" 이라는 말이 두 엔진을 겹쳐 놓은 뷰어에서 눈으로 보입니다. 같은 입력을 두 trace 로 비교하는 "split-screen" 이 Stage 4 의 핵심 구도가 됩니다.
• 옵션 B: DFA minimization. Hopcroft 알고리즘으로 "동작이 같은 DFA state 를 한 블록으로 묶는" 과정을 step-by-step 으로 보여줍니다. 이쪽은 partition refinement 가 주인공이라 Stage 3 과 결이 다른 애니메이션이 필요합니다 — block 이 쪼개지는 장면입니다.

둘 다 재미있는 소재지만, 교육용 프로젝트의 arc 상으로는 옵션 A 가 Stage 2 와의 대비가 강해서 스토리가 깔끔해 보입니다.

어느 쪽이든 DFA 자체를 다시 만들어 쓸 일은 없습니다. Stage 3 의 ConstructionTrace 마지막 step 에 "완성된 DFA" 가 이미 찍혀 있고, 그 state/transition 배열을 다음 stage 가 그대로 물려받습니다. 한 번 만든 artifact 는 다음 stage 의 입력이 됩니다.

Repo: github.com/Ricci-curvature/regex-viz 이번 stage 의 커밋 세 개:

• cbef387 — stage 03: subset construction (NFA → DFA trace)
• 40ed64f — artifacts: regenerate stage03
• 382c24e — stage 03: viz components (ConstructionViewer + DfaGraph)