regex-viz

COUNT: 05

> PROJECTS

> regex-viz[01]

Thompson's Construction, Visible

regex 를 그래프가 아니라 타임라인으로 보기. Stage 1 — NFA 가 자라는 여섯 규칙을, slider 로 스크럽해서 직접 돌려보기.

_Rust_TypeScript_React_MDX_dagre

SOURCE

> regex-viz[02]

NFA, Watching It Match

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

_Rust_TypeScript_React_MDX_dagre

SOURCE

> regex-viz[03]

From NFA to DFA, One Subset at a Time

Stage 3 — NFA 의 active 집합을 DFA 의 state 하나로 승격합니다. Rabin-Scott subset construction 을 slider 로 스크럽하며 DFA 가 subset 하나씩 자라나는 과정을 따라갑니다.

_Rust_TypeScript_React_MDX_dagre

SOURCE

> regex-viz[04]

Side by Side: NFA vs DFA

Stage 4 — 같은 regex 와 같은 입력을 NFA 시뮬레이터와 DFA 시뮬레이터에 동시에 흘려 넣습니다. 왼쪽 pane 에서는 active 집합이 움직이고, 오른쪽 pane 에서는 단일 DFA state 하나만 이동합니다. 두 엔진의 verdict 가 항상 일치하는지도 summary 로 못박아 둡니다.

_Rust_TypeScript_React_MDX_dagre

SOURCE

> regex-viz[05]

Hopcroft DFA Minimization

Stage 5 — 같은 language 를 받아들이는 DFA 중 가장 작은 것을 찾습니다. Hopcroft 의 partition refinement 는 accept / non-accept 두 블록에서 시작해, 어떤 symbol 로 움직였을 때 서로 구분되는 state 들을 발견할 때마다 block 을 쪼갭니다. 더 이상 쪼갤 수 없을 때가 최소 DFA 입니다.

_Rust_TypeScript_React_MDX_dagre

SOURCE