编译技术2-3

Finite Automata for Regular Expressions 正则表达式的有限自动机实现

1. Finite Automata Basics 有限自动机基础 (1) 核心组件 | 组件 | 英文 | 描述 | 图示符号 | |------|------|------|----------| | 状态 | State | 系统可能处于的条件 | 圆形节点 | | 起始状态 | Start State | 初始状态 | 带"Start"箭头的圆形 | | 接受状态 | Accepting State | 成功终止状态 | 双圈圆形 | | 转移 | Transition | 状态间的转换规则 | 带标签的箭头 |

NFA与DFA详解：非确定性与确定性有限自动机

1. NFA (非确定有限自动机)

(1) 核心特性

特性	英文描述	示例图示	重要性
多路径转移	Multiple transitions per input		允许并行尝试
ε-转移	Spontaneous state jumps		实现零成本跳转
非确定性	No unique execution path	同一输入可进入不同状态	理论计算模型

(2) 模拟算法

def simulate_nfa(nfa, input_str):
    current_states = ε_closure({nfa.start})
    for char in input_str:
        next_states = set()
        for state in current_states:
            next_states.update(ε_closure(move(state, char)))
        current_states = next_states
    return nfa.accept in current_states

时间复杂度：O(mn²)
• m: 输入字符串长度

• n: 自动机状态数

🧾 算法描述 Algorithm Description

1. 初始化状态集合： Initialize the set of current states:

初始时，将当前状态集合设为起始状态以及通过ε（空）转移可达的所有状态。

Start with the start state and all states reachable via ε-moves.

2. 遍历输入字符串： For each character in the input:

对于输入字符串的每个字符，重复以下过程。

3. 维护下一状态集合： Maintain a set of next states:

初始化一个空集合用于存放下一步可能到达的状态。

Initially, this set is empty.

4. 状态转移处理： For each current state:

对于当前状态集合中的每个状态：
- 查找所有以当前输入字符为标签的转移（即边）。
  
  Follow transitions labeled with the current character.
- 将这些目标状态加入下一状态集合。

5. 处理 ε-move： Add ε-closure of next states:

对于每个通过字符转移得到的状态，再加入它能通过ε-move（空转移）到达的所有状态。

Add every state reachable via ε-moves to the next states.

6. 更新当前状态集合： Update current states:

将“下一状态集合”更新为新的“当前状态集合”，用于处理下一个字符。

⏱️ 时间复杂度 Time Complexity

复杂度：O(m · n²)

Complexity: O(m · n²)

其中 m 是输入字符串的长度（number of characters in the input string）。
n 是自动机中的状态数量（number of states in the automaton）。
每处理一个字符，可能需要遍历所有状态，并在每个状态中进行 ε-闭包的计算，这可能涉及到最多 O(n) 个状态。

For each character, we may process up to n states and for each, compute ε-closure involving up to n states.

🧩 小结 Summary

步骤	中文描述	English Description
初始化	起始状态及ε可达状态	Start state + ε-closure
遍历字符	对每个字符处理状态转移	For each input character
状态转移	按字符进行转移	Follow transitions by character
ε-闭包	加入所有ε可达状态	Add ε-move reachable states
更新状态	当前状态 ← 下一状态集合	Current states ← Next states
总复杂度	O(m · n²)	O(m · n²)

2. DFA (确定有限自动机)

(1) 核心特性

特性	英文描述	与NFA对比	优势
唯一转移	Exactly one transition per input	不允许多路径	执行效率高
无ε-转移	No spontaneous jumps	必须显式消耗输入	确定性执行
完全映射	Full transition function	每个状态需定义所有输入转移	避免未定义行为

(2) 状态转移表示例

// C语言风格DFA转移表
int dfa[STATE_NUM][ALPHABET_SIZE] = {
    [0] = {'a':1, 'b':2},  // 状态0的转移
    [1] = {'a':1, 'b':3},   // 状态1的转移
    [2] = {'a':1, 'b':4}    // 状态2的转移
};

3. NFA vs DFA 对比分析 (1) 结构差异

graph TD
    NFA -->|允许| MultiPath[多路径转移]
    NFA -->|允许| Epsilon[ε-转移]
    DFA -->|禁止| SinglePath[单路径转移]
    DFA -->|禁止| NoEpsilon[无ε转移]

(2) 能力与效率 | 维度 | NFA | DFA | 胜出方 | |------|-----|-----|--------| | 表达能力 | 与DFA等价 | 与NFA等价 | 平手 | | 构造难度 | 容易(Thompson法) | 复杂(子集构造) | NFA | | 执行效率 | O(mn²) | O(m) | DFA | | 内存占用 | 低(共享结构) | 高(完全展开) | NFA |

DFA/NFA 模拟与优化 DFA/NFA Simulation & Optimization Notes

✅ DFA 示例与转换表

DFA（确定性有限自动机）示例： DFA 的定义包括：

状态集合（如 A, B, C, D）
输入符号（如 0, 1）
转移函数 T(state, symbol) 指定状态在输入某个符号后跳转到哪个新状态

对应的转移函数：

1 2	T(A, 0) = C T(B, 0) = D T(C, 0) = A T(D, 0) = B T(A, 1) = B T(B, 1) = A T(C, 1) = D T(D, 1) = C

Transition Table 转移表：

	0	1
A	C	B
B	D	A
C	A	D
D	B	C

🚀 模拟代码 Simulation Code

代码片段 C++（伪代码）：

int kTransitionTable[kNumStates][kNumSymbols] = {
  {2, 1}, // A → C, B
  {3, 0}, // B → D, A
  {0, 3}, // C → A, D
  {1, 2}  // D → B, C
};

bool kAcceptTable[kNumStates] = {
  true, true, true, false
};

bool simulateDFA(string input) {
  int state = 0;  // Start at state A
  for (char ch : input) {
    state = kTransitionTable[state][ch - '0'];
  }
  return kAcceptTable[state];
}

说明 Explanation：

状态用数字表示（如 A=0，B=1，C=2，D=3）
输入字符转换为索引（如 '0' - '0' = 0，'1' - '0' = 1）
simulateDFA 模拟输入串是否被 DFA 接受

⏱️ 匹配效率 Matching Efficiency

类型	时间复杂度	说明
NFA	O(m · n²)	最坏情况下需在每个字符处理所有状态及 ε 转移
DFA	O(m)	每个输入字符只需一步转移即可处理

英文说明 English:

NFA (Nondeterministic Finite Automaton) may have multiple transitions or ε-moves per character, so matching can take O(m·n²).
DFA (Deterministic Finite Automaton) has exactly one transition per state per input, so matching is linear: O(m).
That’s why we convert NFAs into DFAs before matching — speed!

✨ NFA ➜ DFA 转换（子集构造法）

Subset Construction Algorithm （子集构造）是一种“美丽的算法”，可以将 NFA 转换为 DFA，使匹配变快！

基本思想 Idea：

一个 DFA 状态对应一组 NFA 状态的集合（例如：{A, B, C}）
每个集合在读取某个符号后，转移到另一个状态集合

📌 小结 Summary

项目 Item	NFA	DFA
状态转移	可多重、含 ε 转移	唯一确定
模拟复杂度	O(m · n²)	O(m)
转换方法	-	子集构造法 Subset Construction
匹配速度	慢	快
应用场景	正则表达式，灵活匹配	高效字符串识别