正规文法（3 型 / 右线性）#

形如 A→aB 或 A→a（A、B∈V_N，a∈V_T）。绝大部分程序设计语言的单词都能用正规文法描述。

正规式和正规集（递归定义）#

1. ε 和 ∅ 是 Σ 上的正规式，表示正规集 {ε} 和 ∅。
2. 任意 a∈Σ，a 是正规式，表示正规集 {a}。
3. 若 e₁、e₂ 是正规式，正规集为 L(e₁)、L(e₂)，则：
   • (e₁) → L(e₁)
   • e₁|e₂ → L(e₁) ∪ L(e₂) （或/并）
   • e₁·e₂ → L(e₁)·L(e₂) （连接）
   • e₁* → (L(e₁))* （闭包）
4. 仅有限次使用上述规则得到的才是正规式。

正规式代数规则（🟡）#

• 交换律：r|s = s|r（并可交换）
• 结合律：r|(s|t)=(r|s)|t、r(st)=(rs)t
• 分配律：r(s|t)=rs|rt、(s|t)r=sr|tr（成立）
• 幂等：r|r=r；与 ε：rε=εr=r
• ⚠️ rs ≠ sr：连接不满足交换律。

🔴 正规式 ↔ 正规文法 互相转换#

① 正规式 → 正规文法：令 S→r，反复分解直到每条产生式最多含一个终结符：

• A→xy ⟹ A→xB, B→y
• A→x*y ⟹ A→xA, A→y
• A→x|y ⟹ A→x, A→y

例：R=a(a|d)* → S→aB, B→aB|dB|ε

② 正规文法 → 正规式：反向合并直到只剩开始符定义、右部无非终结符：

• A→xB, B→y ⟹ A=xy
• A→xA, A→y ⟹ A=x*y
• A→x, A→y ⟹ A=x|y

例：S→dA|eB, A→aA|b, B→bB|c → R=(da*b)|(eb*c)

DFA（确定的有穷自动机）#

M = (K, Σ, f, S, Z)

• K：有穷状态集
• Σ：输入字母表
• f：转换函数，K×Σ→K（单值映射，一个状态一个输入只到一个状态）
• S：唯一初态
• Z⊆K：终态集
• 特征：单值、单初态、无 ε 弧。

接受：若 f(S,α)∈Z，则串 α 被 DFA 接受。

重要结论：V⊆Σ* 是正规集 ⟺ 存在 DFA M 使 V=L(M)。

NFA（不确定的有穷自动机）#

M = (K, Σ, f, S, Z)

• f：K×Σ→2^K（映射到状态集的幂集，一个输入可到多个状态）
• S：初态集（可多初态）
• 特征：可多值、可多初态、可有 ε 弧。

重要结论：

• 每个 NFA M 都存在等价 DFA M₁，使 L(M)=L(M₁)。
• DFA 是 NFA 的特例。
• NFA、正规式、正规文法三者等价、可互相转换。

算法 1：语言描述 → 正规式#

根据自然语言约束写正规式。

• 例：“由 a、b 组成、倒数第二个字符为 a” → (a|b)*a(a|b)
• 例：“以 a 开头、后跟任意个 a 或 d” → a(a|d)*

算法 2：正规式 → NFA（Thompson 构造法）#

逐结构地拼接小 NFA：

• R=ε：X —ε→ Y
• R=a：X —a→ Y
• R=st（连接）：N(s) 的终态 —ε→ N(t) 的初态。
• R=s|t（并）：新增初/终态，用 ε 弧分别连到 N(s)、N(t)。
• R=s*（闭包）：新增初/终态，加 ε 弧；N(s) 终态→初态加 ε 弧，新初态→新终态加 ε 弧。

算法 3：NFA → DFA 确定化（子集构造 / 造表法）#

关键运算：

• ε-closure(I)：I 中状态经任意条 ε 弧能到达的状态集（一定包含状态自身）。
• move(I,a)：I 中状态经一条 a 弧到达的状态全体。
• I_a = ε-closure(move(I,a))。

步骤：

1. 表第 0 行/列作标识。
2. 第 1 行第 1 列填 ε-closure(S)。
3. 对已确定的状态集 I，逐个输入符 aⱼ 计算 I_{aⱼ}；若是新集合，补到表尾空行第一列。
4. 重复第 3 步，直到不再产生新状态。
5. 重命名各新状态。含原 NFA 终态的新状态即为 DFA 终态。

算法 4：DFA 最小化（分割法）#

目标：无多余状态、无相互等价状态。

• 多余状态：从初态出发任何输入串都不可达的状态。
• 等价条件：
  1. 一致性：s、t 同为可接受态或同为不可接受态。
  2. 蔓延性：对所有输入符号，s、t 都转到等价的状态。

步骤：

1. 第一步必须先分两组：终态组 / 非终态组。
2. 对每组，按各状态经同一输入到达的状态所属组是否相同，逐步细分；不同则拆开。
3. 直到不能再分为止。
4. 每组合并为一个状态（消除等价态），去掉多余状态。