Brzozowski 导数

把正则表达式看成“尚待匹配的语言”，导数便是从语言中“剥离”已经读掉的前缀后，为了最终接受而仍可读取的后缀语言。匹配过程因而不必维护当前位置或回溯栈，只需反复把语言本身向前推进；不同前缀若产生同一剩余语言，就对应同一个 DFA 状态。关键在于导数是语义运算，而不是简单删掉表达式开头的字符：并、连接和 Kleene 星号都要按可空性规则传播。连接规则中的两项尤其容易漏：读到的 $a$ 可以由左部分 $R$ 消费；若 $R$ 能生成空字，也可以直接由右部分 $S$ 消费，所以必须把两种剩余情况取并。

图中使用的是 $R=a{b}^{\ast }$，即一个 a 后跟任意多个 b：读 a 后剩余式为 $b^{\ast }$，再读任意个 b 都仍为 $b^{\ast }$。图中 $\nu (R_3)=\epsilon$，所以 abb 结束时可空而接受，a 也接受，空输入却不接受。下面的 $(ab{)}^{\ast }$ 把整段 ab 一起重复，括号改变了语言。

对 $R=(ab{)}^{\ast }$，$D_a(R)=b(ab{)}^{\ast }$，再对 $b$ 求导回到 $(ab{)}^{\ast }$。

Brzozowski 的有限性定理保证：把并按结合律、交换律、幂等律规范化，并消去空语言及空字连接中的平凡项后，只有有限多个不同的规范导数，因此可用队列枚举它们来构造 DFA。这些恒等式只识别一部分语言等价式；构造会终止，却不保证所得 DFA 已最小。若完全不做化简，语法上不同但语言等价的导数可能无限膨胀。左商的语义有限性与规范导数的有效有限性，都不保证状态数小或朴素表达式表示紧凑。

令 $R=(a|b{)}^{\ast }abb$。因为前面的星表达式可空，第一次求导得到 $D_a(R)=R+bb$：这个 a 既可能属于任意前缀，也可能是结尾 abb 的开头。接着读 b 得 $R+b$，再读 b 得 $R+\epsilon$，此时可空而接受。保留 $R$ 那一项，意味着即使已匹配出一个 abb，后续仍可以继续寻找新的结尾。以 $R=ab|ac$ 为更小的例子，有 $D_a(R)=b|c$、$D_b(D_a(R))=\epsilon$，所以 ab 被接受，而 $D_d(D_a(R))=\varnothing$，所以 ad 被拒绝。

导数的语法表示可能迅速膨胀，例如交换律、幂等律下等价的并表达式会产生许多不同写法。实际构造需要规范化或按语言等价合并状态；若把“表达式文本相同”误当作“语言相同”，得到的自动机通常远大于必要规模。

导数为正则表达式匹配、等价检查和 DFA 构造提供统一方法，尤其适合函数式实现、符号字母表和按需生成状态的匹配器。反复求导并对等价导数做商，可以从 正则表达式理路正则表达式Regular expression从空语言、空字与单符号语言出发，经并、连接和 Kleene 星有限构造的语言表达式。 直接构造 DFA理路确定性有限自动机Deterministic finite automaton · DFA以有限状态和总转移函数为每个输入字规定唯一运行的识别模型。，给出 Kleene 定理的一条算法化证明路径。增量词法分析也可每读一个字符就更新当前残余语言，并用可空性判断是否已形成完整 token；与 确定化构造理路DFA–NFA 等价定理DFA–NFA equivalence · Subset construction每个 NFA 都能以当前可能状态集为一个 DFA 状态，从而在有限字上保持语言不变。 相比，这种做法把状态生成推迟到实际可达的残余语言上。