◌ Glyph — watch a regex appear from examples

Give it a handful of strings that should match and a handful that shouldn't. Glyph finds the shortest regular expression consistent with all of them — then compiles that regex through NFA → DFA → minimized DFA and lets you watch a string walk the automaton state by state.

No dependencies. No API keys. No build step. Everything runs in the browser.

Live: from the contains “ab” examples, Glyph synthesizes /^.*ab.*$/, draws its 3‑state minimal DFA, then steps the string baabab through it — lighting up each state as a character is read, ending on the accepting state q2.

---

Why it's interesting

Most "regex tools" test a regex you already wrote. Glyph goes the other way: it does program synthesis — it writes the regex for you from examples — and then shows the automata theory underneath, animated.

• Provably shortest. The synthesizer is a uniform‑cost search over a small regex grammar, so the first consistent pattern it finds is guaranteed minimal‑cost — not a lucky heuristic guess.
• Language‑aware search. Candidates are de‑duplicated by language (canonical minimized‑DFA signature), not by syntax. Since regular operations are congruences w.r.t. language equality, this is sound — and it collapses the thousands of syntactic spellings of the same language (a*a* ≡ a*, .|a ≡ .) into one node, making the search tractable.
• The automata are real. Thompson construction, subset construction, and Moore minimization are implemented from scratch and visualized — the picture is the actual minimized DFA, and the highlighted walk is the actual run.

A simpler case: from the ends with “b” examples, Glyph searched 37 candidate languages in 20 ms and returned /^.*b$/, compiled to a 2‑state minimal DFA. (The hardest built‑in puzzle, contains “ab” above, takes ~7,175 candidate languages and a 12‑state NFA → 7‑state DFA → 3‑state minimal DFA.)

---

Run it

It's a static site — just open index.html, or serve the folder:

python -m http.server 8000      # then visit http://localhost:8000

(A tiny HTTP server is recommended over file:// so the synthesis Web Worker and ES‑module imports load cleanly.)

Deep‑link a preset to auto‑synthesize on load: index.html?auto=1.

Tests

Pure‑Node, zero‑dependency engine tests (synthesis correctness + DFA equivalence against the native engine, checked exhaustively over short strings):

npm test        # node test/run.js  →  30 passed, 0 failed

---

How it works

examples ──▶ synthesize (UCS over regex grammar, language‑deduped) ──▶ regex
                                                                         │
                                  parse ──▶ Thompson NFA ──▶ subset DFA ─┤
                                                                         ▼
                                              Moore‑minimized DFA ──▶ animate

File	Role
src/synth.js	Regex synthesis from +/− examples (uniform‑cost search, language de‑dup)
src/automata.js	Parser, Thompson NFA, subset‑construction DFA, Moore minimization, runner
src/viz.js	SVG renderer + step animation of a string through the DFA
src/worker.js	Runs synthesis off the main thread (keeps the UI responsive)
src/app.js	UI glue
src/presets.js	Built‑in puzzles
test/run.js	Engine test harness

Supported regex grammar

Concatenation, alternation |, Kleene star *, plus +, optional ?, grouping ( ), character classes [abc] / ranges [a-z], and . (any symbol in the alphabet). The alphabet is inferred from the example strings.

Limits (by design)

• Regular languages only — no backreferences or lookarounds (those aren't regular, and wouldn't map to a DFA).
• The alphabet is the set of characters seen in the examples; . means "any of those". Matching and visualization live in that finite alphabet.
• Synthesis is bounded by cost/time budgets. Hard targets over a larger alphabet may exhaust the budget and report "no concise regex found" rather than hang.

---

License

MIT © 2026 HiMedia13