正则表示

官官方信息技术老师·9 页·深入（追求细节与边界）·0 次浏览·2 天前
✦ 正则表示信息技术正则表示正则表示和语言
正则语法匹配引擎DFA/NFA性能边界

正则表示

从语法到匹配引擎，彻底搞懂正则的细节、边界与陷阱

按 空格/→ 演示下一步

1 / 9 页

全部页面点击任意一页，跳回舞台从这页播放

正则语法匹配引擎DFA/NFA性能边界

正则表示

从语法到匹配引擎，彻底搞懂正则的细节、边界与陷阱

1第 1 页 · 正则表示

单一终结状态的NFA

单一终结状态的NFA：定义、要点与典型应用

单一终结状态的NFA
单一终结状态的NFA：定义、要点与典型应用
2第 2 页 · 单一终结状态的NFA

正则语言的运算性质

前两页我们把正则语言和NFA、正则表达式画上了等号。自然的问题是：拿到两个正则语言，能不能组合出新的正则语言？哪些运算不会让我们「跑出」这个集合？

三则运算封闭
L₁∪L₂、L₁L₂、L₁*仍是正则的：拼接NFA或加ε转移即可构造
补运算封闭
L̅正则：先把NFA确定化为DFA，再交换终态与非终态
交与差封闭
L₁∩L₂、L₁\L₂正则：经De Morgan律化为补+并
逆运算封闭
L^R正则：把NFA转移箭头反向、起终态互换
同态与逆同态
字符串替换h(L)、h⁻¹(L)仍正则：前者改记号、后者改状态
不漏水的容器对应 →正则语言对运算封闭

水（正则语言）在容器内折腾（并、连接、星、补……），永远渗不出去变成「非正则」

L1∩L2=L1‾∪L2‾‾L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}
3第 3 页 · 正则语言的运算性质

正则表示和语言

前页用 ∪、·、* 操作正则语言，但还缺一个核心问题：每个正则表示 r 究竟对应哪个语言集合 L(r)？这一页给出 L 的归纳定义，并揭示正则表示与正则语言的双向等价。

语义映射 L(r)
每个正则表示 r 唯一对应语言 L(r) ⊆ Σ*，称为 r 表示的语言
归纳基础
L(∅)=∅, L(ε)={ε}, L(a)={a}（对每个 a∈Σ）
归纳步骤
复合时按子表示 r₁、r₂ 的语言递归组合 ∪、连接、闭包
双向等价
正则表示必标记正则语言；每个正则语言也必有某正则表示标记它
菜谱对应 →正则表示 r

菜谱是文字形式（语法），所有按它做出的菜肴构成对应集合（语义）

L(∅)=∅, L(ε)={ε}, L(a)={a}L(r1+r2)=L(r1)∪L(r2), L(r1r2)=L(r1)L(r2), L(r∗)=L(r)∗\begin{aligned}&L(\varnothing)=\varnothing,\ L(\varepsilon)=\{\varepsilon\},\ L(a)=\{a\}\\&L(r_1+r_2)=L(r_1)\cup L(r_2),\ L(r_1r_2)=L(r_1)L(r_2),\ L(r^*)=L(r)^*\end{aligned}
4第 4 页 · 正则表示和语言

正则表示和正则语言

前几页从归纳定义、单一终结状态NFA、运算封闭性几个角度拆解过正则表示和正则语言。这一页把视角收拢：它们到底是什么、如何互相刻画、又用在哪里。

归纳构造
基础项：∅、ε、a∈Σ；归纳项：并 r₁|r₂、连接 r₁r₂、闭包 r₁*。最小集闭合于这三运算。
正则语言
若存在正则表示 r 使 L(r)=L，则 L 是正则语言。L(r) 由 r 的结构递归定义。
等价刻画
Kleene 定理：正则语言 ⟺ 被某 DFA/NFA/ε-NFA 接受 ⟺ 被某正则表示描述
典型应用
编译器词法分析、grep/sed/awk 文本处理、表单与协议字段校验、DNA/日志序列模式挖掘。
菜谱对应 →正则表示

原料=符号、|='换一种'、连接='接着下'、*='重复任意次'，一张菜谱描述一桌菜

L(∅)=∅,  L(ε)={ε},  L(a)={a},  L(r1∣r2)=L(r1)∪L(r2),  L(r1r2)=L(r1)⋅L(r2),  L(r∗)=⋃i≥0L(r)iL(∅)=∅,\;L(ε)=\{ε\},\;L(a)=\{a\},\;L(r₁|r₂)=L(r₁)∪L(r₂),\;L(r₁r₂)=L(r₁)·L(r₂),\;L(r^*)=\bigcup_{i\geq0}L(r)^i
5第 5 页 · 正则表示和正则语言

正则语言的同态

前页讲了正则表示等价于正则语言。那对正则语言做某种'变形'——把每个字母替换成固定串——结果还正则吗？这就是同态要回答的问题。

同态定义
字母表 Σ 上的函数 h: Σ→Σ*，每个字母映成一个固定串
扩展到串与语言
递归 h(xy)=h(x)h(y)；h(L)={h(w) | w∈L} 即逐串替换
封闭性
L 正则 ⇒ h(L) 仍正则；可让 NFA 每条输入边读 h(a)
典型应用
证明正则语言对替换(substitution)封闭的关键一步
逐字翻译规则对应 →字母表同态

每个字母有固定译法，整句翻译后语言类别不变

h(ε)=ε,h(xy)=h(x) h(y)h(\varepsilon) = \varepsilon,\quad h(xy) = h(x)\,h(y)
6第 6 页 · 正则语言的同态

正则表示的代数定律

同态让我们在不同正则语言之间整体切换；想直接在表达式本身上下刀——代数定律登场。

交换律与结合律
并运算可交换可结合；连接运算只可结合、不可交换（一般 RS≠SR）
单位元与零元
ε 是连接单位元（εR=Rε=R）；∅ 是并的单位元、又是连接的零元（∅R=R∅=∅）
分配律
连接对并可左、右分配：R(S+T)=RS+RT，(S+T)R=SR+TR
幂等律
R+R=R，把「重复选择」合并为单次——化简时常常第一个用上
初等代数运算定律对应 →正则表示的运算定律

都是用来化简表达式；区别在于连接不交换、并有幂等性

R(S+T)=RS+RTR(S+T) = RS + RT
7第 7 页 · 正则表示的代数定律

本节要点

  • ✓正则表示用∪、·、*三大递归运算定义语言，与有限自动机等价
  • ✓从正则表示到单一终结状态NFA的构造是等价性证明的关键
  • ✓正则语言对并、连接、星闭包、同态及逆同态均封闭
  • ✓代数定律（如分配律、幂等律）可用于证明两表示等价
  • ✓易错：∅与ε不同，星闭包必含ε
延伸主题：子集构造法：NFA转DFA泵引理判定非正则语言上下文无关文法：再上一阶
8第 8 页 · 本节要点

课后思考

先独立思考，再看参考答案的提示。三题覆盖核心、应用与边界。

1为什么 Thompson 构造会自然产生'多终结状态'的 NFA？改造为'单一终结状态'的思路是什么？

参考答案Thompson 构造按语法递归，每个子表达式对应独立'片段'，需要自己的起止状态才能拼接，故天然多终结。改造方法是新增唯一终结状态，从所有原终结状态引 ε 弧指向它。

2同态 h 下，h(L*) 与 (h(L))* 是同一个集合吗？写出你的证明思路。

参考答案是同一个集合。L* 中串是 L 中串的拼接，h 保持拼接（h(xy)=h(x)h(y)），所以 h 逐段作用再拼接得到 (h(L))*；反向同理。三行即可证毕。

3正则表示的分配律 r(s+t)=rs+rt 无条件成立吗？星号介入后会出现什么反例？

参考答案标准正则表示（并、连接、Kleene 星）上无条件成立，按语言展开即可。但 r(s+t)* ≠ (rs+rt)*——星号改变结构，分配律不能随意代入带星号的子表达式，例如 ab(c+d)* 与 (abc+abd)* 就不相等。

9第 9 页 · 课后思考
正则表示 · 知识图解