# DFA Engine
The DFA engine consumes bytes, follows a deterministic transition table, and emits match outputs according to accepting states. Its correctness is defined by engine invariants plus CPU interpreter parity.
## Invariants
Deterministic: the same transition table, start state, accepting states, and input bytes produce identical output bytes on every run.
NoOutputLost: every match emitted by the CPU DFA interpreter appears in backend output.
NoDuplicateOutput: each logical match key `(pattern_id, end_offset, start_offset when tracked)` appears at most once.
OutputOrdered: matches are emitted in increasing input offset; ties use stable pattern id order.
## Random Test Generation
Generate random valid transition tables with a fixed state count, byte alphabet mapping, start state, accepting-state metadata, and output ids. Generate random input byte strings, including empty input, repeated bytes, all-byte sweeps, and long runs that revisit the same states.
Invalid tables are rejected by validation. Valid tables must not crash, loop indefinitely, or read outside transition storage.
## Verification
For each generated case, run the CPU DFA interpreter and backend engine. Verify determinism by running the backend at least twice, then check no output is lost, no output is duplicated, and output ordering matches the CPU reference. Any failure persists the table and input as a regression with `Fix: make transition lookup, accepting-state emission, and output compaction match the CPU DFA interpreter`.