正规式（正则表达式）与正规集是形式语言理论中的核心概念，广泛应用于编译原理中的词法分析阶段

正规式（正则表达式）与正规集是形式语言理论中的核心概念，广泛应用于编译原理中的词法分析阶段。它们通过三种基本运算——或（|）、连接（・）、闭包（*）——递归地构造出能够描述特定字符串模式的表达式。

1. 核心概念：正规式与正规集

• 定义逻辑：

  • 正规式是一个由字母表 Σ 上的符号经过有限次应用“或”、“连接”、“闭包”运算生成的表达式。
  • 对应的正规集是该正规式所能匹配的所有字符串组成的集合。

• 运算规则补充说明：

  • 连接A·B表示先出现 A 的串，紧接着出现 B 的串；
  • 或A|B表示可以是 A 的串或 B 的串；
  • 闭包A*表示 A 出现任意多次（包括0次），即 ε（空串）、A、AA、AAA… 都属于该集合。

• 优先级与省略规则：

  • 闭包*优先级最高 → 然后是连接・→ 最后是或|；
  • 如ab*|c实际上等价于(a(b*)) | c。

示例解析（Σ = {a, b}）：

2. 正规式的代数性质

这些性质用于正规式的化简和等价变换，在自动机最小化和优化中非常有用：

• 交换律（仅对｜成立）：
  $ U|V = V|U $

• 结合律：
  $ (U|V)|W = U|(V|W) $
  $ (UV)W = U(VW) $

• 分配律：
  $ U(V|W) = UV|UW $
  $ (U|V)W = UW|VW $

• 闭包恒等式：
  $ \varepsilon* = \varepsilon $ （空串的闭包仍是空串）
  $ V** = V* $ （闭包的闭包等于自身）

• 其他常见恒等式：

  • $ \varnothing* = \varepsilon $
  • $ U|\varnothing = U $
  • $ U\varnothing = \varnothing $

3. 有限自动机（FA）

有限自动机是用来识别正规集的数学模型，分为两类：

（1）确定有限自动机（DFA）

• 定义为五元组：(S, Σ, f, s₀, Z)

  • S：有限状态集合
  • Σ：输入字母表
  • f：S × Σ → S，确定性转移函数（每种输入唯一决定下一个状态）
  • s₀ ∈ S：唯一初始状态
  • Z ⊆ S：终止状态集合

• 特点：

  • 无歧义：对于每个状态和输入字符，只有一个下一状态；
  • 易于实现为程序。

（2）非确定有限自动机（NFA）

• 转移函数为：f: S × (Σ ∪ {ε}) → 2^S（可映射到状态子集）

• 允许：

  • 多个转移路径（相同输入从同一状态出发到不同状态）
  • ε-转移（不读入字符也能改变状态）

• 优势：

  • 更容易从正规式构造（如 Thompson 构造法）

• 但最终可通过子集构造法转换为等价 DFA。

🔄关键定理：一个语言是某个正规式所表示的语言 ⇔ 它能被某个 FA 识别 ⇒ 即：正规式 ≡ NFA ≡ DFA 在语言能力上等价

补充背景：在词法分析中的作用

在编译器设计中：

• 使用正规式来精确描述词法单元（token），例如：
  • 标识符：letter(letter|digit)*
  • 整数常量：digit+
• 将这些正规式转化为NFA → DFA → 最小化DFA，进而生成高效的词法分析器（如 Lex 工具的工作流程）。