Brzozowski 导数

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

对 $R=(ab{)}^{\ast }$，$D_a(R)=b(ab{)}^{\ast }$，再对 $b$ 求导回到 $(ab{)}^{\ast }$。对表达式做代数化简后，可达的不同导数只有有限多个，从而直接构造 DFA。若不做等价化简，语法上不同但语言等价的导数可能无限膨胀；“有限”指正则语言的不同左商有限，不保证朴素表达式表示自动保持小规模。

令 $R=(a|b{)}^{\ast }abb$。读入第一个字符 $a$ 后，$D_a(R)$ 描述所有能接在这个 $a$ 后面、使整串仍匹配 $R$ 的后缀；继续对输入逐字符求导，最终表达式可空当且仅当原串被接受。以 $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 状态，从而在有限字上保持语言不变。 相比，这种做法把状态生成推迟到实际可达的残余语言上。