Side by Side: NFA vs DFA

Stage 2 에서는 NFA 에 입력을 흘려 넣고, active 집합이 글자마다 어떻게 퍼졌다 좁혀지는지 봤습니다. Stage 3 에서는 그 집합을 DFA 의 state 하나로 승격해 결정적 오토마타를 만들었습니다.

Stage 4 는 두 결과물을 같은 입력 위에 나란히 태웁니다. 왼쪽 pane 에서는 NFA 의 active 집합이 움직이고, 오른쪽 pane 에서는 DFA 의 단일 state 하나만 옮겨갑니다. 한 slider 가 두 엔진을 동시에 움직입니다.

확인하려는 질문은 두 가지입니다. 첫째, 두 엔진의 verdict 가 늘 일치하는가. 이건 summary 필드로 machine-readable 하게 못박습니다. 둘째, 같은 입력을 먹을 때 두 엔진이 얼마나 다른 모양으로 움직이는가. 이건 두 pane 이 나란히 바뀌는 장면으로 보여줍니다.

아래 뷰어의 slider 를 움직여 봅시다. (a|b)*c 가 aabc 를 소비하는 동안, 왼쪽과 오른쪽이 같은 판단을 얼마나 다른 방식으로 만들어내는지 비교해 보세요.

왼쪽 NFA pane 에서는 매 글자마다 여러 노드가 동시에 켜졌다 꺼집니다. 같은 순간 오른쪽 DFA pane 에서는 정확히 하나의 노드 만 강조됩니다. 두 그림은 같은 정보를 담고 있습니다. 다만 NFA 는 비결정성을 active 집합이라는 폭으로 들고 있고, DFA 는 그 폭을 미리 접어서 state 하나에 녹여두었습니다. aabc 의 네 글자 동안 DFA 는 D0 → D1 → D1 → D2 → D3 으로 이동하고, 마지막에 accept state 인 D3 에 멈춥니다.

상단 verdict badge 는 match (agree) 입니다. 두 엔진 모두 accept 를 반환했고 의견이 같다는 뜻입니다. 만약 한쪽만 accept 라면 badge 는 BUG: engines disagree 로 바뀌고 빨갛게 경고합니다. 이 프로젝트가 옳게 돌아간다면 그 빨간 badge 는 나오면 안 됩니다.

이 글은 Stage 4 를 세 commit 에 1:1 로 매핑합니다

구성은 Stage 3 과 같습니다. 코드 커밋, artifact 재생성 커밋, viz 커밋 세 개로 나누었고, 글도 같은 순서로 세 섹션을 이어갑니다. Stage 4 는 Stage 2 의 matcher 와 Stage 3 의 DFA 결과물을 한 화면에 올리는 단계라 Rust 쪽에는 comparison.rs 하나만 추가됐고, viz 쪽에는 기존 NfaGraph / DfaGraph 를 조립한 ComparisonViewer 가 새로 들어왔습니다.

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

Stage 4 — Comparison Trace

Commit: 9eb94fe — stage 04: NFA vs DFA simulator comparison trace

핵심은 src/comparison.rs, CLI 하나, 테스트 10 개입니다. 새 이론을 추가한 커밋은 아닙니다. Stage 2 의 NFA 시뮬레이터와 Stage 3 의 subset construction 결과를 같은 입력으로 동시에 돌리고, 매 step 에 두 엔진의 현재 상태를 같이 찍어냅니다.

왜 새 trace 타입이 또 필요한가

Stage 3 에서도 비슷한 질문을 했는데, 이번에도 답은 같습니다. shape 이 다르면 타입을 나눕니다.

• Trace (Stage 1–2) 는 한 개의 엔진만 다룹니다. NFA 하나와 step 마다 바뀌는 active 하나가 전부입니다.
• ConstructionTrace (Stage 3) 는 NFA 와 DFA 를 둘 다 다루지만, 시간축은 "알파벳을 훑는 BFS" 입니다. 입력 문자열이 개입하지 않습니다.
• ComparisonTrace (Stage 4) 는 NFA 와 DFA 를 모두 담고, 시간축은 입력 문자열의 소비 입니다. 매 step 에 "지금 NFA 의 active 는 무엇이고, DFA 의 current 는 무엇인가" 를 같이 담아야 합니다.

한 타입에 억지로 욱여넣으면 viewer 가 render 할 때마다 trace.kind 로 큰 분기를 타야 합니다. 분기가 늘어날수록 "이 trace 는 무엇을 보여주는가" 라는 질문도 흐려집니다. 포맷을 한 번 pin 하면 이후 수정은 breaking change 가 되므로 (rule 6), 애초에 독립된 타입으로 분리해 두는 쪽이 낫습니다.

ComparisonStep 의 모양

pub struct ComparisonStep {
    pub description: String,
    pub input_pos: usize,
    /// Live NFA state ids (sorted). Empty once the NFA is stuck.
    pub nfa_active: Vec<usize>,
    /// Current DFA state id. `None` once the DFA has no outgoing edge.
    pub dfa_current: Option<usize>,
}

nfa_active 는 Stage 2 의 active 와 같은 역할입니다. dfa_current 는 DFA 가 살아 있으면 state id, 죽었으면 None 입니다. NFA 가 죽는 조건은 "집합이 공집합이 되는 것" 이고, DFA 가 죽는 조건은 "현재 state 에서 이번 글자로 나가는 transition 이 없는 것" 입니다. 두 엔진 모두 한 번 죽으면 다시 살아나지 않습니다.

Step 개수는 항상 1 + N + 1

입력 길이가 N 이면 trace 는 항상 1 init + N consume + 1 verdict step 을 갖습니다. 중간에 엔진이 죽어도 빈 active / None current 상태를 유지한 채 step 을 계속 emit 합니다. 이유는 하나입니다. 두 pane 이 같은 slider 를 공유하기 때문입니다.

Stage 2 의 matcher 는 NFA 가 공집합으로 떨어진 뒤 아직 입력이 남아 있으면 루프를 끊었습니다. 단일 엔진 trace 에서는 그게 자연스럽습니다. 하지만 Stage 4 에서 step 수가 입력 길이와 달라지면 slider 가 가리키는 prefix 를 독자가 다시 추론해야 합니다. comparison trace 에서는 죽은 상태도 1급 장면으로 남깁니다. "이 글자 이후로 양쪽 엔진이 더 이상 갈 곳이 없다" 는 사실 자체가 화면에 보여야 하기 때문입니다.

verdict: 문장은 description, 판정은 summary

마지막 step 의 description 은 사람이 읽는 문장입니다.

• verdict: NFA match, DFA match — agree
• verdict: NFA reject, DFA reject — agree
• verdict: NFA match, DFA reject — BUG: engines disagree

문장으로 보면 편하지만, 테스트나 viewer 가 이 문자열을 파싱해서 판정하면 쉽게 깨집니다. 그래서 최종 판정은 별도의 summary 로 올렸습니다.

pub struct ComparisonSummary {
    pub nfa_accepted: bool,
    pub dfa_accepted: bool,
    pub verdicts_agree: bool,
}

nfa_accepted 는 "마지막 step 의 nfa_active 에 NFA accept state 가 들어있는가" 입니다. dfa_accepted 는 "마지막 step 의 dfa_current 가 Some(id) 이고, 그 DFA state 의 is_accept 가 참인가" 입니다. verdicts_agree 는 두 bool 이 같은지 미리 계산한 값입니다.

처음에는 이름을 nfa_accept_reached / dfa_accept_reached 로 둘지 고민했습니다. 접은 이유는 "accept state 에 도달한 적이 있다" 로 읽힐 수 있기 때문입니다. ab × "abc" 가 좋은 예입니다. 두 번째 글자 b 를 읽은 직후에는 NFA 와 DFA 모두 accept 에 있습니다. 하지만 세 번째 글자 c 를 읽으면 둘 다 죽고, 최종 verdict 는 reject 입니다. regex 매칭에서 중요한 질문은 "중간에 accept 를 본 적이 있는가" 가 아니라 "전체 입력을 소비한 뒤 accept 에 남아 있는가" 입니다. 그래서 accepted 가 더 정확합니다.

테스트 전략: 기존 matcher 와 교차 검증

comparison 의 NFA arm 은 Stage 2 의 matcher::simulate 와 같은 verdict 를 내야 합니다. 테스트 하나를 이 교차 검증에 할애했습니다.

#[test]
fn comparison_matches_matcher_verdict_on_every_pin() {
    use crate::matcher;
    for (regex, input) in PINS {
        let cmp = run_comparison(regex, input).unwrap();
        let tr = matcher::run_trace(regex, input).unwrap();
        let last = tr.steps.last().unwrap();
        let matcher_accepted = last.input_pos == Some(input.chars().count())
            && last.active.contains(&last.nfa.accept);
        assert_eq!(cmp.summary.nfa_accepted, matcher_accepted);
    }
}

comparison.rs 안에는 epsilon_closure / char_move 구현이 다시 들어 있습니다. matcher 의 함수들이 private 이라 그대로 재사용하지 않았고, 각 module 이 자기 알고리즘을 한 파일 안에서 읽히게 두고 싶었습니다. 대신 이 테스트가 두 복제본 사이의 어긋남을 잡아줍니다. 별도의 engines_agree_on_every_stage2_pin 테스트는 열두 pin 에 대해 verdicts_agree == true 를 확인합니다. 서로 다른 경로로 계산해도 같은 정답에 도달한다는 것을 stage 전체에 걸쳐 못박는 assertion 입니다.

Stage 4 — Pinned Artifacts

Commit: 15ffef3 — artifacts: regenerate stage04

Stage 2 에서 썼던 (regex, input) pin 열두 개를 그대로 재사용했습니다. 같은 pin 을 다시 돌리는 이유는 간단합니다. Stage 4 의 두 엔진 verdict 가 Stage 2 의 standalone matcher 결과와 완전히 일치해야 정답입니다. 새 입력을 늘리기보다 이미 손으로 확인해 둔 pin 을 그대로 들고 오는 편이 comparison 의 목적에 더 맞습니다.

열두 개 모두 summary.verdicts_agree 가 true 입니다. 하나라도 false 가 나온다면 NFA 시뮬레이터, subset construction, DFA walk 중 어딘가에 버그가 있다는 뜻입니다. 그때 가장 빠른 디버깅 방법은 viewer 를 켜고 두 pane 이 어느 step 에서 갈라지는지 보는 것입니다.

a × "a" — 가장 작은 대비

NFA 쪽은 init 에서 {0} 으로 시작해 a 를 읽고 {1} 로 이동합니다. DFA 쪽은 D0 → D1 입니다. 단일 글자라 두 엔진이 거의 같은 그림처럼 보이지만, 집합 vs 단일 노드라는 차이는 이미 여기서 드러납니다. NFA pane 의 노드는 "현재 active 집합의 원소" 로 켜지고, DFA pane 의 노드는 그 집합 전체를 접어 만든 이름으로 켜집니다.

a × "b" — 두 엔진이 같은 step 에 죽습니다

a 를 기대하는 regex 에 b 를 먹였습니다. consume step 에서 NFA 의 active 는 공집합으로 떨어지고, DFA 의 current 는 None 이 됩니다. 두 pane 모두 "살아 있는 state 가 없음" 을 표현합니다. NFA 는 어떤 노드도 강조하지 않고, DFA 는 focus 를 지웁니다. verdict badge 는 회색 reject (agree) 입니다.

ab × "abc" — accept 를 지나쳤다가 죽는 장면

이 케이스가 Stage 4 에서 가장 교육적입니다. step 을 따라가 봅시다.

• init: NFA {0}, DFA D0.
• a 소비 후: NFA {1,2}. a 의 accept 와 concat ε 로 이어진 b 의 start 가 같이 살아 있습니다. DFA 는 D1.
• b 소비 후: NFA {3}. 전체 regex 의 accept 입니다. DFA 는 accept state 인 D2. 이 순간 두 엔진 모두 accept 에 있습니다.
• c 소비 후: NFA 의 char_move 가 공집합을 뱉고, DFA 는 D2 에서 c transition 을 찾지 못해 None 으로 떨어집니다. 두 엔진 모두 죽습니다.

최종 verdict 는 reject (agree) 입니다. "accept 에 도달한 적이 있는가" 로 물으면 둘 다 true 이지만, "전체 입력을 소비한 뒤 accept 에 있는가" 로 물으면 둘 다 false 입니다. 이 차이가 accepted 라는 이름을 고른 이유입니다. regex 매칭은 중간 checkpoint 가 아니라 마지막 상태로 판정합니다.

a* × "" — consume step 이 없는 케이스

step 은 init 과 verdict 둘뿐입니다. 입력이 비었기 때문입니다. NFA 는 init 에서 이미 {0,2,3} 에 있고, state 3 은 bypass ε 덕분에 들어온 accept 입니다. DFA 는 D0 에 있으며, D0 자체가 accept 로 마킹되어 있습니다. badge 는 match (agree) 입니다. 0 글자도 입력이다 라는 점이 양쪽 엔진에서 같은 방식으로 표현됩니다. NFA 는 init active 에 accept 가 들어 있어서, DFA 는 start state 자체가 accept 라서 match 입니다.

a* × "aab" — 마지막 글자에서 동시에 무너지는 장면

a 두 번은 양쪽이 부드럽게 넘깁니다. 문제는 b 입니다. NFA 의 active 에는 b transition 을 탈 수 있는 state 가 없어서 공집합으로 떨어지고, DFA 쪽도 현재 state 에서 b transition 을 찾지 못해 None 으로 빠집니다. 두 엔진이 같은 글자에서 동시에 죽습니다. 이 동기화가 Stage 4 의 본질입니다. 결정성의 차이는 "같은 입력을 먹으면 같은 판단을 한다" 는 계약 위에서만 의미가 있습니다.

(a|b)*c × "abab" — 끝까지 살아 있지만 reject

a 와 b 를 번갈아 먹는 동안 NFA active 는 (a|b)* 루프 안을 맴돌고, DFA 는 D1 과 D2 사이를 오갑니다. 두 엔진 모두 죽지는 않았지만 accept 에도 도달하지 못한 채 입력이 끝납니다. 마지막 step 에서 NFA pane 에는 여러 노드가 여전히 켜져 있고 (c 를 기다리는 상태), DFA pane 에서는 non-accept state 인 D2 가 focus 되어 있습니다. 그래서 badge 는 회색 reject (agree) 입니다.

"reject" 에도 두 가지 모양이 있습니다. 중간에 갈 곳이 없어 죽는 reject 와, 끝까지 읽었지만 accept 밖에서 멈추는 reject 입니다. a_star__miss 는 전자이고, a_or_b_star_c__miss 는 후자입니다. summary 에서는 둘 다 nfa_accepted: false 로 찍히지만, 화면에서는 마지막 상태가 [] / null 인지, 아직 살아 있는 non-accept state 인지로 구분됩니다.

pinning 의 의미

Stage 1–3 과 같습니다. 이 글의 viewer 들은 15ffef3 에 고정 되어 있어서, 이후에 comparison.rs 를 리팩터링하거나 description 문장을 손봐도 여기 보이는 step 수, active 집합, verdict 는 그대로 유지됩니다. 포맷 자체 (ComparisonTrace) 가 바뀐다면 stage04 전체를 regenerate 하고 이 포스트도 함께 갱신해야 합니다. 그래서 code 커밋과 artifact 재생성 커밋을 분리했습니다.

match 케이스 세 개가 왜 embed 에서 빠졌나

ab__match, a_or_b__match_a, a_star__match, a_or_b_star_c__match 도 pin 에는 있지만 대부분 embed 하지 않았습니다. 두 엔진이 부드럽게 match 로 흘러가는 장면은 a × "a" 와 메인 viewer 의 (a|b)*c × "aabc" 에서 이미 충분히 보입니다. 반대로 reject 케이스는 어디에서, 어떻게 실패하는지가 두 엔진의 구조 차이를 더 잘 드러냅니다.

그래도 ab × "ab" 하나는 참고로 남겨둡니다. DFA 는 D0 → D1 → D2 로 이동하고, NFA 는 {0} → {1,2} → {3} 으로 대응됩니다. 두 엔진의 "같은 의미, 다른 모양" 이 가장 짧은 concat 예제에서 한 화면에 나옵니다.

Stage 4 — Viewer

Commit: 2ff140e — stage 04: viz components (ComparisonViewer)

위 viewer 들은 전부 이 커밋의 산물입니다. 두 파일을 추가하고, viz/README.md 한 줄을 갱신했습니다.

viz/
├── comparison.ts         ← src/comparison.rs 의 TypeScript mirror (~30 loc)
└── ComparisonViewer.tsx  ← 2-pane + InputStrip + slider + verdict badge (~200 loc)

왜 ConstructionViewer 를 확장하지 않았나

Stage 3 의 ConstructionViewer 도 NFA + DFA 2-pane 구조였습니다. 하지만 확장해서 한 컴포넌트로 합치지는 않았습니다.

1. 시간축이 다릅니다. ConstructionViewer 의 slider 는 "subset construction 의 BFS step" 을 움직입니다. ComparisonViewer 의 slider 는 "입력 문자열의 prefix" 를 움직입니다. 같은 UI 안에 두 축이 섞이면 독자가 slider 의 의미를 매번 다시 해석해야 합니다.
2. 오른쪽 pane 의 의미가 다릅니다. ConstructionViewer 의 DFA pane 은 "지금까지 발견된 DFA" 를 보여주고, step 이 진행되면서 노드가 추가됩니다. ComparisonViewer 의 DFA pane 은 완성된 DFA 전체 를 처음부터 보여주고, 그 위에서 focus 만 이동합니다.
3. InputStrip 은 ComparisonViewer 에만 필요합니다. Construction trace 에는 입력 문자열이 없으므로 strip 을 그릴 이유가 없습니다.

결국 두 컴포넌트는 NfaGraph / DfaGraph 를 공유하지만, 그 위의 shell 은 따로 둡니다. 그 shell 이 바로 "이 stage 가 무엇을 보여주는가" 를 결정합니다.

Verdict badge

상단 헤더에는 작은 verdict badge 를 달았습니다.

• 초록색 match (agree) — 두 엔진 모두 accept, 의견 일치.
• 회색 reject (agree) — 두 엔진 모두 reject, 의견 일치.
• 빨간색 BUG: engines disagree — 한쪽만 accept. 이 프로젝트가 옳게 돌아간다면 나오면 안 되는 색입니다.

단순히 bool 세 개를 색으로 매핑한 것이지만, 효과는 큽니다. viewer 를 열자마자 "이 입력은 match 인가 reject 인가" 를 알 수 있고, 그 다음 slider 로 "왜 그렇게 됐는가" 를 확인할 수 있습니다. 결과를 숨겨두고 맞히게 하는 UI 가 아니라, 결론을 먼저 보여주고 경로를 탐색하게 하는 UI 입니다.

InputStrip 의 미묘한 사례

Stage 2 의 TraceViewer 에도 비슷한 InputStrip 이 있었지만, 이번에는 빈 입력 까지 고려해야 합니다. a* × "" 에서 chars.length === 0 이면 (empty input) 회색 텍스트를 대신 그립니다. 그렇지 않으면 strip 자리가 0px 높이로 접혀서 layout 이 위아래로 튀는 느낌을 줍니다.

input_pos 는 "여기까지 읽었다" 는 위치입니다. 그래서 init step 의 input_pos = 0 은 첫 글자를 가리키고, 한 글자를 소비한 뒤의 input_pos = 1 은 다음 글자를 가리킵니다. verdict step 에서는 input_pos === chars.length 이므로 어떤 글자에도 highlight 가 걸리지 않습니다. 이건 의도한 동작입니다. 마지막 consume step 과 verdict step 을 구분하려면, "이제 더 읽을 글자가 없다" 는 상태를 빈 highlight 로 표현하는 편이 가장 명확했습니다.

Lessons

1. 두 엔진을 공유 slider 에 태우려면 step 수를 맞춰야 합니다. 한쪽이 죽더라도 죽은 상태로 step 을 계속 찍어주는 것이 가장 단순한 해법이었습니다. Stage 2 matcher 처럼 중간에 break 해버리면 trace 길이가 입력에 따라 달라지고, comparison viewer 에서는 slider 의 의미가 흐려집니다. 죽은 상태 (nfa_active: [], dfa_current: null) 를 1급 시각 상태로 받아들여야 두 pane 이 같은 시간축 위에 놓입니다.

2. summary 와 description 의 역할을 분리해야 합니다. 마지막 step 의 description 은 사람이 읽기 좋은 문장이고, summary 는 테스트와 viewer 가 읽는 계약입니다. 문자열 문장을 machine contract 로 쓰면, 문장만 다듬어도 테스트가 깨지는 이상한 구조가 됩니다. 일반화하면 machine contract 와 human narration 을 같은 필드에 겸업시키지 말 것 입니다.

3. epsilon_closure / char_move 가 세 번째로 복제되었습니다. matcher.rs, dfa.rs, comparison.rs 에 거의 같은 구현이 나란히 있습니다. 프로덕션 코드라면 공통 helper 로 빼는 게 맞겠지만, 이 프로젝트에서는 "이 module 하나만 읽어도 알고리즘이 보인다" 는 장점이 아직 더 큽니다. 복제본이 서로 어긋날 위험은 교차 검증 테스트로 막습니다.

다음 — Stage 5

DFA Minimization (Hopcroft). 같은 regex 라도 subset construction 이 뱉어내는 DFA 에는 "동작이 같은 state" 가 남아 있을 수 있습니다. 예를 들어 (a|b)*c 의 경우 D0, D1, D2 는 모두 non-accept 이고, a/b/c 에 대해 같은 방식으로 이동합니다. 이 셋은 하나로 합쳐도 language 가 바뀌지 않습니다.

Hopcroft 알고리즘은 모든 state 를 "accept / non-accept" 두 블록으로 나누는 데서 시작합니다. 그 다음 "같은 블록 안에 있는데 어떤 symbol 로 이동하면 서로 다른 블록으로 간다" 는 state 들을 찾아 블록을 쪼갭니다. 더 이상 쪼갤 수 없을 때 각 블록이 최소 DFA 의 state 하나가 됩니다.

애니메이션 관점에서도 Stage 3–4 와 결이 다릅니다. Stage 3 이 "새 state 가 등장하는 장면" 이었고 Stage 4 가 "focus 가 이동하는 장면" 이었다면, Stage 5 는 "블록이 쪼개지는 장면" 입니다. 같은 regex 를 Stage 3, Stage 4, Stage 5 로 이어서 보면 subset construction → simulation → minimization 이 어떤 관계로 엮이는지 세 각도에서 보입니다.

그 뒤 Stage 6 에는 backtracker 를 붙여 "NFA/DFA 는 멀쩡한데 backtracker 만 폭발한다" 는 대비를 보여줄 계획입니다. (a+)+b × "aaaaa!" 같은 입력에서 backtracker 는 path 수가 급격히 늘어나지만, Stage 4 의 NFA/DFA 시뮬레이터는 여전히 입력 길이에 맞춰 몇 step 만에 끝납니다. 그 대비가 "왜 regex 엔진 설계에서 알고리즘 선택이 중요한가" 에 대한 가장 좋은 시각 자료가 될 겁니다.

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

이번 stage 의 커밋 세 개:

• 9eb94fe — stage 04: NFA vs DFA simulator comparison trace
• 15ffef3 — artifacts: regenerate stage04
• 2ff140e — stage 04: viz components (ComparisonViewer)