[形式语言与自动机] 正则语言与正则表达式

正则语言的定义#

正则语言是在有限字母表 $\Sigma$ 上的一个集合，其中包含的元素是所有能被一个正则表达式/DFA/NFA识别的字符串，正则语言是 $\Sigma^*$ 的一个子集

正则表达式的定义#

正则表达式是一个字符串，使用特定的语法规则来描述一个正则语言。正则表达式和DFA、NFA之间是等价的，即它们识别的正则语言是相同的

\text{正则表达式} \Leftrightarrow \text{DFA} \Leftrightarrow \text{NFA}

正则表达式由以下基本元素组成，且以下每个元素本身也是一个正则表达式：

空集：表示一个不包含任何字符串的语言，通常用符号 $\emptyset$ 表示
空字符串：表示一个只包含空字符串的语言，通常用符号 $\epsilon$ 表示
单个符号：对于每个输入符号 $a \in \Sigma$ ，表示一个只包含字符串 $a$ 的语言
连接：如果 $R$ 和 $S$ 是正则表达式，那么 $RS$ 表示连接操作，表示由 $R$ 中的字符串连接 $S$ 中的字符串组成的语言，或多次连接，例如 $R^n$ 表示由 $R$ 中的字符串连接 $n$ 次组成的语言， $R^0=\{\epsilon\}$
选择：如果 $R$ 和 $S$ 是正则表达式，那么 $R|S$ 表示选择操作，表示由 $R$ 中的字符串或 $S$ 中的字符串组成的语言
闭包：如果 $R$ 是一个正则表达式，那么 $R^*$ 表示闭包操作，表示由 $R$ 中的字符串重复零次或多次组成的语言

一个正则表达式通过有限次上述操作后生成的仍然是一个正则表达式，因此正则表达式可以递归定义

TIP
正闭包： $R^+$ 表示由 $R$ 中的字符串重复一次或多次组成的语言，即 $R^+ = RR^*$
克林闭包： $R^*$ 表示由 $R$ 中的字符串重复零次或多次组成的语言，即 $R^* = \{\epsilon\} \cup R^+$
运算顺序：括号 > 闭包 > 连接 > 选择

例子#

设计一个正则表达式匹配所有包含110但不能包含111的二进制字符串

可以使用以下正则表达式：

(0+10)^*110(110+0+10)^*(1+11+\epsilon)

DFA/NFA转正则表达式#

e.g. 现有一DFA，状态转移表如下：

状态	输入0	输入1
$\rightarrow q_0$	$q_1$	$q_0$
$q_1$	$q_2$	$q_0$
$\ast q_2$	$q_2$	$q_2$

状态消除法#

添加唯一的开始状态和接受状态(实际上这么处理完已经变NFA了)：

状态	输入0	输入1	$\epsilon$
$\rightarrow S$	-	-	$q_0$
$q_0$	$q_1$	$q_0$	-
$q_1$	$q_2$	$q_0$	-
$\ast q_2$	$q_2$	$q_2$	$F$
$\ast F$	-	-	-

逐个消除中间状态：

经过步骤1后，中间状态是 $q_0$ 和 $q_1$ ，我们可以先消除 $q2$ ：

关注要消除的状态的入边、自环和出边，将其替换为一个新的正则表达式，公式为：

\text{入边表达式} \cdot (\text{自环表达式})^* \cdot \text{出边表达式} + \text{入边来源到出边目标原有表达式}

$q_2$ 入边： $q_1 \xrightarrow{0} q_2$ ，则表达式为 $0$
$q_2$ 自环： $q_2 \xrightarrow{0} q_2, q_2 \xrightarrow{1} q_2$ ，则表达式为 $0+1$
$q_2$ 出边： $q_2 \xrightarrow{\epsilon} F$ , 则表达式为 $\epsilon$

所以消去 $q_2$ 后，只有一个来源和一个目标，则只有 $q_1$ 到 $F$ 的边， $q_1$ 到 $F$ 的表达式为：

0(0+1)^*\epsilon + \text{无} = 0(0+1)^*

当前状态转移为：

S \xrightarrow{\epsilon} q_0, \quad q_0 \xrightarrow{0} q_1, \quad q_1 \xrightarrow{1} q_0, \quad q_0 \xrightarrow{1} q_0, \quad q_1 \xrightarrow{0(0+1)^*} F

消 $q_1$ :

入边： $q_0 \xrightarrow{0} q_1$ ，则表达式为 $0$
自环： $q_1$ 没有自环，则表达式为 $\epsilon$
出边： $q_1 \xrightarrow{0(0+1)^*} F, q_1 \xrightarrow{1} q_0$ ，则表达式有 $0(0+1)^*$ 与 $1$

则 $q_0$ 到 $F$ 的表达式为：

0 \cdot (\epsilon)^* \cdot 0(0+1)^* + \varnothing = 00(0+1)^*

$q_0$ 到 $q_0$ 的表达式为：

注意 $q_0$ 到 $q_0$ 已存在转移(自环)，不要忘记并上

0 \cdot (\epsilon)^* \cdot 1 + 1 = 01 + 1

此时，状态转移为：

S \xrightarrow{\epsilon} q_0, \quad q_0 \xrightarrow{01 + 1} q_0, \quad q_0 \xrightarrow{00(0+1)^*} F

消 $q_0$ :

入边： $S \xrightarrow{\epsilon} q_0$ ，则表达式为 $\epsilon$
自环： $q_0 \xrightarrow{01 + 1} q_0$ ，
出边： $q_0 \xrightarrow{00(0+1)^*} F$ ，则表达式为 $00(0+1)^*$

则 $S$ 到 $F$ 的表达式为：

\epsilon \cdot (01 + 1)^* \cdot 00(0+1)^* + \varnothing = (01 + 1)^*00(0+1)^*

则结果为： $(01 + 1)^*00(0+1)^*$

$R^{(k)}_{ij}$ 递推法#

首先为每个状态标注序号(给的DFA已经有了可以直接用)，则 $R^{(k)}_{ij}$ 表示从状态 $i$ 到状态 $j$ ，经过的所有中间状态(中间也就是不包含开始和结束状态)的序号不超过 $k$ 的所有路径的正则表达式。

也就是如果想得到上述DFA的正则表达式，我们需要计算 $R^{(2)}_{02}$

递推公式#

R^{(k)}_{ij} = R^{(k-1)}_{ij} + R^{(k-1)}_{ik} (R^{(k-1)}_{kk})^* R^{(k-1)}_{kj}

含义为：

\begin{aligned} R^{(k)}_{ij} = &\text{不经过状态k就能从状态i到达状态j的所有路径} \\ + &\text{能从i到达状态k但不经过k的所有路径} \\ \cdot &(\text{状态k的自环})^* \\ \cdot &\text{从状态k到达状态j但不经过k的所有路径} \end{aligned}

开始递推：

\begin{aligned} R^{(2)}_{02} &= R^{(1)}_{02} + R^{(1)}_{02} (R^{(1)}_{22})^* R^{(1)}_{22} \\[1em] R^{(1)}_{02} &= R^{(0)}_{02} + R^{(0)}_{01} (R^{(0)}_{11})^* R^{(0)}_{12} = \varnothing + R^{(0)}_{01} (R^{(0)}_{11})^* 0 \\ R^{(1)}_{22} &= R^{(0)}_{22} + R^{(0)}_{22} (R^{(0)}_{22})^* R^{(0)}_{22} = (0 + 1)^* +(0 + 1)^* ((0 + 1)^*)^* (0 + 1)^* = (0 + 1)^* \\[1em] R^{(0)}_{01} &= R^{(-1)}_{01} + R^{(-1)}_{00} (R^{(-1)}_{00})^* R^{(-1)}_{01} = 0 + 1 \cdot (1)^* \cdot 0 = 1^*0 \\ R^{(0)}_{11} &= R^{(-1)}_{11} + R^{(-1)}_{10} (R^{(-1)}_{00})^* R^{(-1)}_{01} = \varnothing + 1 \cdot (1)^* \cdot 0 = 11^*0 \end{aligned}

所以：

\begin{aligned} R^{(1)}_{02} &= 1^*0 (11^*0)^* 0\\ R^{(1)}_{22} &= (0 + 1)^* \\[2em] R^{(2)}_{02} &= R^{(1)}_{02} + R^{(1)}_{02} (R^{(1)}_{22})^* R^{(1)}_{22} \\ &= 1^*0 (11^*0)^* 0 + 1^*0 (11^*0)^* 0 ((0 + 1)^*)^* (0 + 1)^* \\ &= 1^*0 (11^*0)^* 0 (0 + 1)^* \\ \end{aligned}

正则语言的定义#

正则表达式的定义#

例子#

DFA/NFA转正则表达式#

状态消除法#

Rij(k)R^{(k)}_{ij}Rij(k)​递推法#

递推公式#

$R^{(k)}_{ij}$ 递推法#