Brzozowski derivative

Summary

The Brzozowski derivative of a formal language $L$ by a word $u$ is the set of words $v$ with $uv$ in $L$. For a regular expression it can be computed symbolically, by simple rules on the structure of the expression. Testing whether a word belongs to a language then reduces to repeated derivation followed by a check for the empty word. Derivatives give a direct way to build a deterministic finite automaton from a regular expression, and they are closely tied to the Myhill–Nerode theorem.