## 3.1 规则式

$$(01)* + (10)* + 0(10)* + 1(01)*\\ = (\varepsilon +1)(01)*(\varepsilon +0)$$

## 3.2 DFA 和 RE

### 3.2.1 DFA 转 RE

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

$$R_{ij}^{(k)} = R_{ij}^{(k-1)} + R_{ik}^{(k-1)} (R_{kk}^{(k-1)})^* R_{kj}^{(k-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*0(0+1)*$$

### 3.2.2 状态消除法

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

## 3.3 RE 的代数法则

### 3.3.1 基本规则

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

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

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

$$(a+b)^*=(a^*b^*)^*$$

### 3.3.2 R 规则

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

\begin{align} R&=aR+b\\ &=a(aR+b)+b\\ &=a^2R + ab + b\\ &=a^2(aR+b) + ab + b\\ &=a^3 R + a^2b + ab + b\\ &\quad\cdots\\ &=(a^n + a^{n-1} + \cdots + a^2 + a + \varepsilon )b\\ &=a^*b \end{align}