DFA Validator

A drop-in replacement for regex-based validation in hot paths. $O(n)$ time, constant memory, zero heap allocations. Built for a high-traffic service where every microsecond counts.

Why

Regex engines can have unpredictable performance. For validation that runs on every request, a precomputed DFA gives consistent, measurable latency.

The complexity is straightforward:

Architecture

The validator uses a precomputed transition table. Each input symbol maps to the next state in $O(1)$ time. See the paper on regex and DFAs for the full derivation.

Tech stack

Go, generated transition tables.