为何正则表达式引擎不支持交、补、差等全部集合运算？

从自动机理论的角度来看，正则表达式对应的有限自动机（Finite automata, FA）在并、交、补、差四类集合运算下是完全封闭的，同时还支持连接、Kleene星这两类正则表达式常用运算的封闭性。

目前主流正则实现都原生支持连接、并、Kleene星三类运算，但几乎都没有原生支持交、补、差这类集合运算，核心原因有三点：

• 语法兼容成本过高：现有正则语法已经经过数十年的迭代，不同语言、不同工具的实现存在大量差异化的语法扩展，新增集合运算的语法符号会带来极高的历史兼容风险，几乎没有厂商愿意推进这类修改
• 核心实现难度大：交、补运算的正确实现需要基于确定有限自动机（DFA）做状态构造，而目前绝大多数主流正则引擎都采用基于非确定有限自动机（NFA）的回溯实现，要支持集合运算需要完全重构核心匹配逻辑，开发和维护成本都极高
• 实际需求不足：90%以上的日常正则使用场景不需要集合运算能力，少量需要这类能力的场景可以通过多个正则分步校验、现有语法组合的方式间接实现，需求侧不足以推动厂商付出成本做原生支持

公开的自动机课程讲义中有相关的FA构造示例，演示了包含子串01和1的个数为奇数两个有限自动机的交集运算构造过程，可以直观验证有限自动机的交集封闭性。

Scott Aaronson. 6.045J 自动机、可计算性与复杂度. 2011年春季学期. 麻省理工学院MIT开放课程资源，许可协议：Creative Commons BY-NC-SA。

内容的提问来源于stack exchange，提问作者BEVR1337