RICCILAB
> projects/regex/nfa-watching-it-match
> REGEX-VIZ|STATUS: ACTIVE|

NFA, Watching It Match

Stage 2 — 오토마타는 그대로 있고 입력만 흐릅니다. 글자 하나하나가 지날 때마다 active 집합이 어떻게 퍼졌다 좁혀지는지, ε-closure 와 char-move 로 따라가 봅니다.

_Rust_TypeScript_React_MDX_dagre
SOURCE →

Stage 1 에서는 오토마타가 자라는 모습을 봤습니다. AST 를 따라 state 와 ε 이 하나씩 붙어가던 과정입니다.

Stage 2 에서는 오토마타가 멈춰 있고, 대신 입력이 흐릅니다. 변하는 것은 active 하나입니다. 지금 이 순간 동시에 머물고 있는 state 들의 집합입니다. 이 집합이 글자마다 퍼졌다가 좁혀지는 장면이 NFA 의 N, 그러니까 비결정성이 실제로 돌아가는 순간입니다.

뷰어는 Stage 1 과 같습니다. 보는 시간대만 바뀝니다.

아래 뷰어의 slider 를 움직여 봅시다. (a|b)*c 가 입력 aabc 를 소비하는 동안, 글자마다 어떤 state 들이 "켜져" 있는지 추적합니다.

abεεεεεεεεcε0123456789
step 1 / 6start: ε-closure({6})10s · 12t
aabc

글자 하나를 읽을 때마다 여러 노드가 동시에 노랗게 켜집니다. 바로 여기서 NFA 의 성격이 드러납니다. "지금 나는 state N 에 있다" (결정론) 가 아니라 "지금 state {0, 2, 4, 6, 7, 8} 에 동시에 있다" (비결정론) 는 뜻입니다. Stage 2 는 이 집합을 step 단위로 찍어내는 작업이라고 보면 됩니다.

이 글은 Stage 2 를 두 commit 에 1:1 로 매핑합니다

Stage 1 은 commit 이 세 개 (code / artifacts / viz) 였지만, Stage 2 는 viz 를 재사용한 덕에 두 개 로 끝납니다. 코드 커밋 하나와 artifact 재생성 커밋 하나입니다. 커밋 수는 줄었지만, 글을 읽는 흐름은 Stage 1 과 같게 맞췄습니다.

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

Stage 2 — Subset-construction Advance

Commit: 9e1cbde — stage 02: NFA matching trace (subset-construction advance)

src/matcher.rs 한 파일과 CLI 하나, 테스트 10 개가 핵심입니다. viz 쪽은 Stage 1 의 <TraceViewer /> 를 그대로 씁니다. trace.kind === "run" 분기가 이미 컴포넌트 안에 들어있기 때문입니다.

문제 설정 — 빌드했으니 돌려보자

Stage 1 의 산물은 regex 하나당 NFA 하나입니다. a|b*c 를 돌리면 state 10 개와 ε 여러 개가 생깁니다. 그러면 다음 질문은 뻔합니다. 이 NFA 에 문자열을 흘려 넣어서 매칭해 보고 싶습니다.

고전적인 접근은 크게 두 갈래입니다.

  • Backtracking simulator. DFS 로 내려가다가 막히면 "다른 branch 로 되돌아가 다시 시도" 하는 방식입니다. Python re, Perl, Java 의 기본 엔진이 이쪽입니다. 구현은 단순하지만, pathological regex ((a+)+b 에 aaaaa! 같은 입력) 에서는 지수 시간으로 터집니다.
  • Subset-construction advance. 가능한 state 들을 한꺼번에 끌고 가는 방식입니다. 입력 한 글자마다 집합을 한 번만 이동합니다 — 지금 집합이 {2, 4} 이고 a 를 읽으면 다음 집합은 {5, 7} 이 되는 식입니다. 1968 년 Ken Thompson 이 grep 에 쓴 방식으로, 시간 복잡도는 선형입니다.

Stage 2 에서 구현한 것은 두 번째입니다. 구현이 단순한 것도 이유지만, 더 큰 이유는 "NFA 의 N 은 동시에 여러 state" 라는 정의가 코드 동작에 그대로 드러난다는 점입니다. backtracker 는 Stage 4 에서 따로 붙여 두 엔진을 나란히 비교할 예정입니다.

알고리즘 세 줄

active := ε-closure({ nfa.start })
for each char c in input:
    active := ε-closure( char-move(active, c) )
end

match  ⟺  nfa.accept ∈ active  AND  모든 입력 소비됨

핵심은 ε-closure 입니다. ε transition 은 입력을 소비하지 않으므로, state s 에 있다는 말은 곧 s 에서 ε 로 도달 가능한 모든 state 에도 이미 와 있다는 뜻입니다. 그래서 매 step 시작 지점과 char_move 직후에 ε-closure 를 한 번씩 걸어 "지금 진짜로 살아있는 집합" 으로 정리합니다.

src/matcher.rs 핵심

pub fn simulate(nfa: Nfa, input: &str) -> Trace {
    let chars: Vec<char> = input.chars().collect();
    let mut steps: Vec<Step> = Vec::new();
 
    let mut current = epsilon_closure(&nfa, [nfa.start]);
    steps.push(Step {
        description: format!("start: ε-closure({{{}}})", nfa.start),
        nfa: nfa.clone(),
        active: sorted(&current),
        input_pos: Some(0),
    });
 
    let mut stuck_at: Option<usize> = None;
    for (i, c) in chars.iter().enumerate() {
        if current.is_empty() {
            stuck_at = Some(i);
            break;
        }
        let moved = char_move(&nfa, &current, *c);
        current = epsilon_closure(&nfa, moved);
        steps.push(Step {
            description: format!("consume '{c}' at pos {i} → {}", i + 1),
            nfa: nfa.clone(),
            active: sorted(&current),
            input_pos: Some(i + 1),
        });
    }
    // ... verdict step (아래 참조)
}

epsilon_closure 는 worklist DFS 한 번이고, char_move 는 active 안의 state 중 label == c 인 transition 의 목적지를 모으는 짧은 루프입니다. 둘 다 10 줄 안팎이고 무거운 건 없습니다.

Trace 의 모양

포맷은 Build trace 와 그대로 공유 합니다. Run 쪽에서 달라지는 부분은 이 정도입니다.

  • kind: "run"
  • input 에 원본 문자열이 담깁니다
  • nfa 는 모든 step 에서 같은 스냅샷 — 달라지지 않습니다
  • active 가 그 순간 살아있는 state 집합
  • input_pos 는 현재 커서 위치

TraceViewer 는 Build trace 를 받으면 NFA 가 자라는 모습을, Run trace 를 받으면 NFA 를 고정한 채 active 가 깜빡거리는 모습을 그립니다. trace.kind 한 줄로 분기합니다. 이 통합 덕에 Stage 2 에서는 viz 코드를 한 줄도 건드리지 않았습니다.

세 가지 verdict

run trace 는 항상 init step 으로 시작해 verdict step 으로 닫힙니다. 그 사이에는 입력 글자 수만큼의 consume step 이 들어갑니다. verdict 는 세 경우 중 하나입니다.

  1. match — 입력을 전부 소비했고, 마지막 active 에 accept state 가 들어있는 경우
  2. mismatch, end — 입력은 끝까지 읽었는데 accept 가 active 에 없는 경우
  3. mismatch, stuck — 도중에 active 가 공집합이 되어 남은 입력을 더 읽을 수 없는 경우

제일 단순한 케이스부터 보겠습니다.

a × "a" — match

a01
step 1 / 3start: ε-closure({0})2s · 1t
a

step 은 세 개입니다 — init, consume 'a', verdict. init 의 active = {0} (start state) 입니다. 'a' 를 읽으면 char_move({0}, 'a') = {1} 이고, 이어지는 ε-closure 도 그대로 {1} 입니다. accept (= 1) 가 active 에 들어있으니 match 입니다.

a × "b" — mismatch at end

a01
step 1 / 3start: ε-closure({0})2s · 1t
b

char_move({0}, 'b') = ∅ 이고 ε-closure 를 걸어도 공집합 그대로입니다. active 가 비워집니다. 다만 이 순간 입력도 이미 다 읽은 상태라 루프가 그대로 끝나고, 코드의 "stuck 감지" 분기는 타지 않습니다. verdict 에서 "accept 미포함" 으로 마무리됩니다. 정리하면 stuck 과 end-mismatch 를 가르는 기준은 하나 — 공집합이 된 뒤에 입력이 남아있느냐 입니다.

Concat — 세 가지 운명

같은 regex ab 를 세 가지 입력으로 돌려봅시다.

ab × "ab" — match

abε0123
step 1 / 4start: ε-closure({0})4s · 3t
ab

init active 는 {0} 입니다. a 를 읽으면 이동 자체는 {1} 인데, 뒤이은 ε-closure 가 concat ε-link 를 따라 state 2 까지 끌어와서 {1, 2} 가 됩니다. 글자 하나밖에 안 먹었는데 두 state 에 동시에 머무는 모양입니다. 이게 concat ε-link 의 역할입니다. 그 다음 b 를 읽으면 {3} 으로 좁혀지고 accept 에 도달합니다.

ab × "a" — partial, mismatch at end

abε0123
step 1 / 3start: ε-closure({0})4s · 3t
a

a 를 소비하고 나면 active 는 {1, 2} 입니다. 여기서 입력이 끝납니다. accept (= 3) 이 active 에 없으므로 "mismatch: accept 3 not active at end" 로 마무리됩니다.

ab × "abc" — extra, mismatch at end

abε0123
step 1 / 5start: ε-closure({0})4s · 3t
abc

a, b 까지는 match 와 똑같이 진행됩니다. 문제는 세 번째 글자 c 를 읽는 순간입니다 — char_move({3}, 'c') = ∅ 이 되어 active 가 비어버립니다. 그런데 이 경우도 stuck 으로 잡히지는 않습니다. 공집합이 consume step 의 결과물 로 기록되는 시점에 입력 인덱스는 이미 3 (끝) 에 도달해 있고, 다음 iteration 이 돌지 않기 때문입니다. 결국 빈 active 상태에서 verdict 가 "accept 미포함" 으로 떨어집니다.

"partial" 과 "extra" 가 둘 다 end-mismatch 로 묶이는 것은, 이 엔진이 부분 매칭을 허용하지 않는 설계이기 때문입니다. grep 식의 "입력 어딘가에 패턴이 박혀 있으면 match" 가 아니라, "입력 전체가 regex 에 정확히 맞아야 match" 라는 쪽입니다 — 수학에서 말하는 언어 membership 에 더 가깝습니다. anchored / unanchored 구분은 Stage 5 에서 다룹니다.

Star — init 의 ε-closure 안에 이미 accept 가 들어있는 경우

a* 가 빈 문자열을 삼킬 수 있다는 사실은 Stage 1 에서 "bypass ε" 라는 구조 로 설명했습니다. Stage 2 에서는 같은 사실을 매칭 관점에서 다시 봅니다.

a* × "" — match without consuming

aεεεε0123
step 1 / 2start: ε-closure({2})4s · 5t

step 은 init 과 verdict 둘뿐입니다. new_start (= 2) 에서 new_accept (= 3) 까지 ε 하나로 바로 닿기 때문에, init 의 ε-closure 를 계산하자마자 active = {0, 2, 3} 이 됩니다. 처음부터 accept 가 active 에 들어있으니 입력이 하나도 없어도 match 입니다.

a* × "aab" — mismatch on trailing 'b'

aεεεε0123
step 1 / 5start: ε-closure({2})4s · 5t
aab

a 가 두 번 반복되는 동안 active 는 {0, 1, 3} 근처에서 맴돕니다. 그러다 b 를 만나면 char_move({0, 1, 3}, 'b') = ∅ 이 되어 step 에 공집합이 찍히고 루프가 끝납니다. 이것도 "stuck 탐지가 다음 iteration 에 걸렸다면 stuck 으로 분류됐을" 패턴입니다. 다만 b 가 입력의 마지막 글자였기 때문에 실제 verdict 는 "accept 미포함" 쪽으로 떨어집니다.

Stuck — 중간에 공집합이 되고, 그 뒤에 입력이 남아있는 경우

본래 의미의 stuck — 루프 안에서 active 가 비어 break 가 걸리는 경우 — 을 보려면 active 가 공집합이 된 시점에 아직 입력이 남아있는 케이스가 필요합니다. 그런데 고정해 둔 12 개 케이스에는 그 장면이 정확히 들어간 예가 없습니다. mismatch 쪽 pin 을 전부 "읽을 수 있는 만큼 읽고 입력이 끝나는" 쪽으로 잡았기 때문입니다. 대신 결이 비슷한 사례를 하나 보겠습니다.

(a|b)*c × "abab" — 루프만 돌다가 끝

abεεεεεεεεcε0123456789
step 1 / 6start: ε-closure({6})10s · 12t
abab

a 와 b 를 번갈아 소비하는 동안 active 는 (a|b)* 루프 안쪽을 맴돕니다. 문제는 입력에 c 가 없다는 점입니다. 마지막 b 를 소비한 뒤에도 active 에는 c 로 나갈 수 있는 state 가 남아있지만, 입력이 거기서 끝나버리니 accept (= 9) 에는 끝까지 닿지 못합니다. 결과는 "mismatch: accept 9 not active at end" 입니다.

진짜 중간 stuck 을 눈으로 확인하고 싶다면 cargo run --example 02_run_nfa -- "ab" "axy" 를 직접 돌려보면 됩니다. x 에서 char_move 가 공집합을 뱉고, 다음 iteration 에 진입하면서 current.is_empty() 가 트리거됩니다. 그래서 y 는 아예 시도조차 못 하고 끝납니다. verdict description 에 "no live states at pos 1; remaining "xy"" 가 찍힙니다.

Stage 2 — Pinned Artifacts

Commit: 0d14906 — artifacts: regenerate stage02

run trace 는 열두 개입니다. regex 다섯 개에 입력을 1-3 개씩 붙였습니다.

stage02_names=(
    a__match a__miss
    ab__match ab__partial ab__extra
    a_or_b__match_a a_or_b__miss
    a_star__empty a_star__match a_star__miss
    a_or_b_star_c__match a_or_b_star_c__miss
)
파일regex입력결과
a__match.jsona"a"match
a__miss.jsona"b"mismatch — active 가 공집합, 입력 종료
ab__match.jsonab"ab"match
ab__partial.jsonab"a"mismatch — 입력이 모자람
ab__extra.jsonab"abc"mismatch — accept 지나서 c 만남
a_or_b__match_a.jsona|b"a"match (alt 의 왼쪽 branch)
a_or_b__miss.jsona|b"c"mismatch
a_star__empty.jsona*""match — bypass ε
a_star__match.jsona*"aaa"match — loopback ε 반복
a_star__miss.jsona*"aab"mismatch — trailing b
a_or_b_star_c__match.json(a|b)*c"aabc"match — 루프 후 close
a_or_b_star_c__miss.json(a|b)*c"abab"mismatch — c 가 없음

regex 다섯 개를 고른 기준은 Stage 1 의 세 연산자 (concat, alt, star) 에 중첩 하나를 더한 형태입니다. plus 와 question 은 별도 artifact 를 두지 않고 cargo test matcher::plus / matcher::question 으로만 검증합니다 — 매칭 관점에서 + 와 ? 는 * 의 변주일 뿐이라 시각적으로 새롭게 보일 게 없기 때문입니다.

pinning 의 의미.

Stage 1 에서 쓴 원칙 그대로입니다. 이 글의 뷰어들은 0d14906 에 고정 되어 있어서, 나중에 matcher 구현을 뜯거나 stuck 탐지 시점을 조정하더라도 여기 보이는 step 수와 active 집합과 description 은 그대로 유지됩니다. 글의 시간축과 코드의 시간축을 분리하는 장치입니다.

Trace 포맷이 바뀌면 artifacts/ 전체를 regenerate 하고 관련 포스트도 같이 업데이트해야 합니다. 그래서 포맷 변경은 breaking change 로 취급하고, 코드 변경과는 절대 같은 커밋에 섞지 않습니다. stage 02: 와 artifacts: 를 별개 커밋으로 쪼갠 것도 이 원칙 때문입니다.

Lessons

불안정한 지점이 세 군데 있습니다.

  1. stuck 탐지가 한 step 늦게 걸립니다. char_move 가 공집합을 반환한 순간에는 그냥 "active 가 빈 consume step" 으로 기록되고, 다음 iteration 에 진입할 때에야 current.is_empty() 가 트리거됩니다. 덕분에 "active 가 비워지는 순간" 이 슬라이더에 보이기는 하지만, verdict 분류 (stuck 이냐 end-mismatch 냐) 는 "공집합이 된 뒤에 입력이 남아있느냐" 라는 사후 조건으로 갈립니다. UX 관점에서 치명적이지는 않아도, ab × "abc" 처럼 accept 를 지난 뒤 비워지는 경우와 ab × "axy" 처럼 중간에 비워지는 경우가 description 수준에서 대칭이 아니라는 점이 걸립니다. Stage 4 에서 backtracker 와 나란히 놓을 때 trace 구조를 한 번 정리할 예정입니다.

  2. char_move 의 복잡도가 step 당 O(|states| × |transitions|) 입니다. adjacency map 하나만 만들어두면 O(|active| × 평균 outdegree) 로 내려가지만, Stage 2 에서 다루는 regex 크기에서는 체감이 안 돼서 일단 그대로 둡니다. Stage 4 에서 backtracker 와 성능을 비교하는 trace 를 만들다가 active 가 커지는 regex 가 끼어들면 그때 인덱싱을 붙이기로 했습니다. 조기 최적화는 하지 않습니다.

  3. step 마다 NFA 스냅샷이 통째로 실립니다. Run trace 에서는 NFA 가 불변인데도 step.nfa 자리에 같은 값이 매 step 반복해서 들어갑니다. aabc 정도의 짧은 입력이면 JSON 이 9KB 수준이지만, 입력이 길어지면 선형으로 부풀어오릅니다. Stage 1 에서 예고했던 "delta 모드" 가 현실적으로 필요해지는 지점은 Stage 4 쯤일 테고, 그때 한 번에 정리할 계획입니다. TraceKind::Run 전용으로 nfa 를 trace top-level 에 한 번만 올리고 step 에서는 빼는 게 제일 자연스러운 방향인데, 그러면 build trace 와의 포맷 일치가 깨지는 trade-off 가 생깁니다.

다음 — Stage 3

Subset construction, on paper. NFA 를 DFA 로 컴파일하는 과정입니다.

  • src/dfa.rs — NFA state 집합을 DFA 의 state 하나로 묶는 작업입니다. Stage 2 에서 이미 ε-closure + char_move 를 굴려봤기 때문에, 알고리즘 자체는 "같은 루틴을 입력 문자열이 아니라 알파벳 전체 에 대해 돌리면서 새 DFA state 를 계속 발견" 하는 꼴이 됩니다.
  • examples/03_subset_construction.rs — regex 를 받아 construction-trace JSON 을 뱉는 CLI 입니다. 각 DFA state 가 어떤 NFA state 집합을 접어서 만들어졌는지 매핑까지 같이 기록합니다.
  • Viewer: 같은 <TraceViewer /> 로 풀릴 것 같긴 한데, DFA 노드에 "이 노드는 NFA 의 {3, 4, 7}" 같은 라벨이 붙어야 해서 NfaGraph props 가 한 번은 흔들릴 가능성이 있습니다.

복선은 이미 Stage 2 에 깔려 있습니다. 매 step 의 active 가 하나의 state 가 아니라 집합 이었다는 점입니다. 이 집합 자체를 state 로 승격하면 DFA 가 됩니다. a|b 의 NFA 는 state 가 여섯 개였지만, DFA 로 접으면 state 세 개로 충분합니다.

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

  • 9e1cbde — stage 02: NFA matching trace (subset-construction advance)
  • 0d14906 — artifacts: regenerate stage02
EOF — 2026-04-21