第三章 规则式与规则语言

3.1 规则式

规则式（RE，RegEx，Regular Expression，正则表达式）用于描述字符串的字符组织规则（也即语言）。例如 ：01*+10*，表示 0 开头，后面跟着任意个 1；或者 1 开头，后面跟着任意多个 0.

如果有语言 L, M。则语言的并就是二者所能表示的串的集合的并。语言的连接是二者所能表示的串的连接的集合（“笛卡尔” 连接，意会一下）。语言的闭包：语言自己和自己的任意次连接的集合。

例如 $L = \{0, 1\}$，则 L 的闭包 $L* = \{0,1\}*$ 是所有 0,1 构成的串，0, 00, 000, ..., 01, 10, 11, 100, 101 ...。

例如，所有 01 交替的串的规则式：

3.2 DFA 和 RE

任何 DFA 都可以写成 RE

3.2.1 DFA 转 RE

例子：这个 DFA $A$，接受所有至少一个 0 的串。

假设状态 i 到 j 之间的路径可以用串 w 表示，串 w 的 RE 记作 $R_{ij}^(k)$，路径上没有大于 $k$ 的中间状态。

我们可以穷举出：

1. $R_{11}^{(0)} = \varepsilon + 1$
2. $R_{12}^{(0)} = 0$
3. $R_{21}^{(0)} = \varnothing $
4. $R_{22}^{(0)} = (\varepsilon + 0 + 1)$

根据定理：

代入得：

1. $R_{11}^{(1)} = 1^*$
2. $R_{12}^{(1)} = 1^*0$
3. $R_{21}^{(1)} = \varnothing $
4. $R_{22}^{(1)} = (\varepsilon + 0 + 1)$

同理的继续迭代得到：

1. $R_{11}^{(2)} = 1*$
2. $R_{12}^{(2)} = 1^*0(0+1)^*$
3. $R_{21}^{(2)} = \varnothing $
4. $R_{22}^{(2)} = (0 + 1)^*$

由于 1 是初始状态，2 是接受状态，取 $R_{12}^{(2)}$ 作为最终结果：

3.2.2 状态消除法

3.2.1 的方法，对于一个 n 状态自动机要构造 $n^3$ 个表达式，代价较高。使用状态消除法，将中间状态替换为一个等效的正则表达式，重复此过程，即可完成转换。详见 此文。

3.2.3 RE 转 NFA

定理：所有 RE 定义的语言都可以由 FA 定义。

对于 $r+s$ 型，可以构造为：

对于 $rs$ 型，可以构造为：

对于 $r*$ 型，可以构造为：

例子：将 $(0+1)*1 (0+1)$ 构造为 $\varepsilon-\text {NFA}$

分解，构造 $a*1a$ 的自动机即可，其中 $a = 0+1$

3.3 RE 的代数法则

3.3.1 基本规则

并运算（$+$）满足：

1. 可结合
2. 可交换
3. 幂等
4. 幺元为 $\varnothing$

连接运算（$\cdot$）满足：

1. 可结合
2. 零元为 $\varnothing$
3. 幺元为 $\varepsilon$

连接运算不可交换。

并运算和连接运算可分配。

闭包运算：

1. $(L^*)^* = L^*$
2. $\varnothing^* = \varepsilon$
3. $\varepsilon^* = \varepsilon$
4. $L^* = L^++\varepsilon$
5. $(\varepsilon+L)^* = L^*$

如果两个 RE 表达相同的语言，那么两个规则式等价。例如：

3.3.2 R 规则

R 规则：R = aR + b <=> a*b