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 交替的串的规则式:

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

3.2 DFA 和 RE

任何 DFA 都可以写成 RE

3.2.1 DFA 转 RE

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

image-20210613000730664

假设状态 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)$

根据定理:

$$ 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 是初始状态,2 是接受状态,取 $R_{12}^{(2)}$ 作为最终结果:

$$ 1*0(0+1)* $$

3.2.2 状态消除法

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

3.2.3 RE 转 NFA

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

对于 $r+s$ 型,可以构造为:

image-20210615215829348

对于 $rs$ 型,可以构造为:

image-20210615215848300

对于 $r*$ 型,可以构造为:

image-20210615215903983

例子:将 $(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 表达相同的语言,那么两个规则式等价。例如:

$$ (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} $$