1369 字
7 分钟
[形式语言与自动机] 正则语言与正则表达式
2026-05-30
形式语言与自动机
形式语言与自动机

正则语言的定义#

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

正则表达式的定义#

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

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

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

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

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

TIP

正闭包：R+R^+ 表示由 RR 中的字符串重复一次或多次组成的语言，即 R+=RR∗R^+ = RR^*

克林闭包：R∗R^* 表示由 RR 中的字符串重复零次或多次组成的语言，即 R∗={ϵ}∪R+R^* = \{\epsilon\} \cup R^+

运算顺序：括号 > 闭包 > 连接 > 选择

例子#

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

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

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

DFA/NFA转正则表达式#

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

状态输入0输入1
→q0\rightarrow q_0q1q_1q0q_0
q1q_1q2q_2q0q_0
∗q2\ast q_2q2q_2q2q_2

状态消除法#

  1. 添加唯一的开始状态和接受状态(实际上这么处理完已经变NFA了)：
状态输入0输入1ϵ\epsilon
→S\rightarrow S--q0q_0
q0q_0q1q_1q0q_0-
q1q_1q2q_2q0q_0-
∗q2\ast q_2q2q_2q2q_2FF
∗F\ast F---
  1. 逐个消除中间状态：

经过步骤1后，中间状态是q0q_0和q1q_1，我们可以先消除q2q2：

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

入边表达式⋅(自环表达式)∗⋅出边表达式+入边来源到出边目标原有表达式\text{入边表达式} \cdot (\text{自环表达式})^* \cdot \text{出边表达式} + \text{入边来源到出边目标原有表达式}
  • q2q_2入边：q1→0q2q_1 \xrightarrow{0} q_2，则表达式为00
  • q2q_2自环：q2→0q2,q2→1q2q_2 \xrightarrow{0} q_2, q_2 \xrightarrow{1} q_2，则表达式为0+10+1
  • q2q_2出边：q2→ϵFq_2 \xrightarrow{\epsilon} F, 则表达式为ϵ\epsilon

所以消去q2q_2后，只有一个来源和一个目标，则只有q1q_1到FF的边，q1q_1到FF的表达式为：

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

当前状态转移为：

S→ϵq0,q0→0q1,q1→1q0,q0→1q0,q1→0(0+1)∗FS \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

消q1q_1:

  • 入边：q0→0q1q_0 \xrightarrow{0} q_1，则表达式为00
  • 自环：q1q_1没有自环，则表达式为ϵ\epsilon
  • 出边：q1→0(0+1)∗F,q1→1q0q_1 \xrightarrow{0(0+1)^*} F, q_1 \xrightarrow{1} q_0，则表达式有0(0+1)∗0(0+1)^*与11

则q0q_0到FF的表达式为：

0⋅(ϵ)∗⋅0(0+1)∗+∅=00(0+1)∗0 \cdot (\epsilon)^* \cdot 0(0+1)^* + \varnothing = 00(0+1)^*

q0q_0到q0q_0的表达式为：

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

0⋅(ϵ)∗⋅1+1=01+10 \cdot (\epsilon)^* \cdot 1 + 1 = 01 + 1

此时，状态转移为：

S→ϵq0,q0→01+1q0,q0→00(0+1)∗FS \xrightarrow{\epsilon} q_0, \quad q_0 \xrightarrow{01 + 1} q_0, \quad q_0 \xrightarrow{00(0+1)^*} F

消q0q_0:

  • 入边：S→ϵq0S \xrightarrow{\epsilon} q_0，则表达式为ϵ\epsilon
  • 自环：q0→01+1q0q_0 \xrightarrow{01 + 1} q_0，
  • 出边：q0→00(0+1)∗Fq_0 \xrightarrow{00(0+1)^*} F，则表达式为00(0+1)∗00(0+1)^*

则SS到FF的表达式为：

ϵ⋅(01+1)∗⋅00(0+1)∗+∅=(01+1)∗00(0+1)∗\epsilon \cdot (01 + 1)^* \cdot 00(0+1)^* + \varnothing = (01 + 1)^*00(0+1)^*

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

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

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

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

递推公式#

Rij(k)=Rij(k−1)+Rik(k−1)(Rkk(k−1))∗Rkj(k−1)R^{(k)}_{ij} = R^{(k-1)}_{ij} + R^{(k-1)}_{ik} (R^{(k-1)}_{kk})^* R^{(k-1)}_{kj}

含义为：

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

开始递推：

R02(2)=R02(1)+R02(1)(R22(1))∗R22(1)R02(1)=R02(0)+R01(0)(R11(0))∗R12(0)=∅+R01(0)(R11(0))∗0R22(1)=R22(0)+R22(0)(R22(0))∗R22(0)=(0+1)∗+(0+1)∗((0+1)∗)∗(0+1)∗=(0+1)∗R01(0)=R01(−1)+R00(−1)(R00(−1))∗R01(−1)=0+1⋅(1)∗⋅0=1∗0R11(0)=R11(−1)+R10(−1)(R00(−1))∗R01(−1)=∅+1⋅(1)∗⋅0=11∗0\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}

所以：

R02(1)=1∗0(11∗0)∗0R22(1)=(0+1)∗R02(2)=R02(1)+R02(1)(R22(1))∗R22(1)=1∗0(11∗0)∗0+1∗0(11∗0)∗0((0+1)∗)∗(0+1)∗=1∗0(11∗0)∗0(0+1)∗\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}

可以用我做的小工具regcmp来验证一下，和上面状态消除法得到的结果是等价的

[形式语言与自动机] 正则语言与正则表达式
https://alkaid114.github.io/posts/automata/regex/
作者
Alkaid114
发布于
2026-05-30
许可协议
CC BY-NC-SA 4.0
[形式语言与自动机] CFG上下文无关文法
[形式语言与自动机] NFA非确定有穷自动机
© 2026 Alkaid114. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari
Inspired by Mizuki