形式陈述

语言 $L\subseteq\Sigma^*$$L\subseteq {\mathrm{\Sigma }}^{\ast }$ 对字母 $a$$a$ 的左导数定义为 $a^{-1}L=\{w:aw\in L\}$$a^{-1}L=\{w:aw\in L\}$，对字 $u$$u$ 迭代得到 $u^{-1}L$$u^{-1}L$。正则表达式导数满足 $D_a(R+S)=D_a(R)+D_a(S)$$D_a(R+S)=D_a(R)+D_a(S)$、$D_a(RS)=D_a(R)S+\nu(R)D_a(S)$$D_a(RS)=D_a(R)S+\nu (R)D_a(S)$、$D_a(R^*)=D_a(R)R^*$$D_a(R^{\ast })=D_a(R)R^{\ast }$，其中 $\nu(R)$$\nu (R)$ 表示 $\varepsilon\in L(R)$$\epsilon \in L(R)$。关键判据是 $w\in L(R)$$w\in L(R)$ 当且仅当 $\varepsilon\in L(D_w(R))$$\epsilon \in L(D_w(R))$。

直觉

导数把已经读掉的前缀从语言中“剥离”，剩下的表达式精确描述为了最终接受还允许读什么。不同前缀若产生同一剩余语言，就对应同一个 DFA 状态。

例子与边界

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

推论与应用

导数提供正则表达式匹配、等价检查和 DFA 构造的统一方法，尤其适合函数式实现、符号字母表和按需生成状态的匹配器。

参考资料

• Janusz A. Brzozowski, Derivatives of Regular Expressions, Journal of the ACM 11(4), 1964，pp. 481–494。
• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chs. 1–9。