三、正则表达式理论：从形式语言到自动机实现

一、简介

正则表达式，是计算机科学史上闪闪发光的优秀理论：有好的理论，好的代码，好的程序，应用广泛。

70 年代末，正则表达式已经成为 unix 的关键特性，并且拥有大量以正则表达式为主要功能的优秀程序： ed, sed, grep, egrep, awk, lex。如今，正则表达式在程序设计中被广泛使用。

本文介绍正则表达式的理论和实现，以及我们如何使用它。

二、理论基础：计算理论的基石

正则表达式不仅仅是一种字符串处理工具，它在计算机科学理论（计算理论）中占据着核心地位。

乔姆斯基体系 (Chomsky Hierarchy)

在形式语言理论中，诺姆·乔姆斯基将语言分为四个层级。正则表达式描述的是正则语言 (Regular Language)，这是乔姆斯基体系中第 3 型语言，也是最简单、限制最强、但计算最高效的一类语言。

为什么说它是“好的理论”？

一个优秀的理论通常具备：简洁性、表达力强、且计算上可控。正则表达式完美符合这些特征：

1. 等价性 (Equivalence)：

正则表达式、非确定性有限自动机 (NFA) 和确定性有限自动机 (DFA) 三者在表达能力上是完全等价的。这意味着我们可以用人类易读的正则语法来写规则，然后自动转换为机器执行最高效的 DFA 代码。

2. 封闭性 (Closure Properties)：

正则语言在并集、交集、补集、连接、闭包等运算下都是封闭的。这意味着你可以随意组合两个正则表达式，其结果依然是一个正则表达式，依然可以用有限自动机处理。

3. 可判定性 (Decidability)：

对于正则语言，很多关键问题都是可判定的（有算法能在有限时间内给出 Yes/No）： - 成员性：字符串 \(s\) 是否符合规则 \(R\)？ (匹配问题) - 空性：规则 \(R\) 是否匹配不到任何字符串？ - 等价性：规则 \(R_1\) 和 \(R_2\) 是否描述了同一个集合？

相比之下，对于上下文无关语言（如编程语言语法），“等价性”就是不可判定的。对于图灵完备的系统，连“是否停机”都是不可判定的。

4. 效率保证：

因为等价于 DFA，正则表达式的匹配可以在线性时间 \(O(n)\) 内完成，且只需要常数空间的内存（不考虑输出捕获）。这使得它成为处理海量数据的理想选择。

正则表达式

正则表达式（Regular Expression）是用一个字符串来描述一个集合的规则。 例如 a*b 描述了 “b”, “ab”, “aab”, “aaab”… 这样一个无穷集合。

在计算机科学中，正则表达式等价于有限自动机（Finite Automaton）。 任何一个正则表达式都可以转换为一个等价的非确定性有限自动机（NFA），而 NFA 又可以转换为确定性有限自动机（DFA）。

基本运算

正则表达式有三种基本的运算：

1. 连接 (Concatenation): ab 表示先匹配 a 再匹配 b。
2. 并集 (Union): a|b 表示匹配 a 或者 b。
3. 闭包 (Kleene Star): a* 表示匹配 0 个或多个 a。

其它常见的符号如 +, ?, [] 都可以由这三种基本运算推导出来：

• a+ 等价于 aa*
• a? 等价于 a|ε (ε 表示空串)

常用语法速查 (PCRE)

虽然理论上只需要连接、并集和闭包，但在实际工程中（如 Perl, Python, Java, Go, JavaScript），我们通常使用更丰富的语法（PCRE 标准或其变体）来简化编写。

简单组合示例

四、NFA 构建（Thompson 算法）

Ken Thompson 在 1968 年提出了一种算法，可以将正则表达式直接转换为 NFA。 这个算法非常直观，它基于对上述三种基本运算的递归构造。

1. 单个字符

对于单个字符 a，构造一个简单的 NFA：

2. 连接 (Concatenation) st

对于正则表达式 st，我们将 s 的 NFA 的结束状态与 t 的 NFA 的开始状态合并（或者通过 ε 边连接）。

3. 并集 (Union) s|t

对于 s|t，我们创建一个新的开始状态和结束状态。

• 新开始状态通过 ε 边连接到 s 和 t 的开始状态。
• s 和 t 的结束状态通过 ε 边连接到新结束状态。

4. 闭包 (Kleene Star) s*

对于 s*，我们需要支持重复匹配和 0 次匹配。

• 重复：s 的结束状态有一条 ε 边回到 s 的开始状态。
• 0 次：新开始状态有一条 ε 边直接跳到新结束状态。

五、NFA 模拟执行

构建好 NFA 后，如何用它来匹配字符串呢？ NFA 的特点是，在某一时刻，它可能处于多个状态。

例如对于 a|b，初始时通过 ε 边，自动机同时处于 s 的开始状态和 t 的开始状态。 当我们读入字符 ‘a’ 时，所有处于活动状态的节点，如果有一条 ‘a’ 的边，就转移到下一个状态。

算法流程：

1. 初始集合 \(S = \{start\_node\}\)。
2. 计算 \(S\) 的 ε-闭包 (Epsilon Closure)：即从 \(S\) 中的状态出发，只走 ε 边能到达的所有状态的集合。
3. 读入下一个字符 \(c\)。
4. 对于 \(S\) 中的每个状态，如果能通过 \(c\) 转移，则将目标状态加入新集合 \(Next\)。
5. 令 \(S = \text{epsilon\_closure}(Next)\)。
6. 重复步骤 3-5，直到字符串读完。
7. 如果最终集合 \(S\) 中包含结束状态，则匹配成功。

六、代码实现（C++）

下面是一个简单的正则引擎实现，支持 |, *, () 和连接。

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <set>

using namespace std;

// NFA 状态节点
struct State {
  int id;
  int c; // 匹配字符，256 表示 split (epsilon), 257 表示 match
  State *out;
  State *out1;
  int lastlist; // 用于防止搜索时重复访问

  State(int c, State *out, State *out1) : c(c), out(out), out1(out1), lastlist(0) {
  static int id_cnt = 0;
  id = ++id_cnt;
  }
};

// NFA 片段
struct Frag {
  State *start;
  vector<State**> out; // 未连接的输出指针列表
};

// 辅助函数：创建状态
State* state(int c, State *out, State *out1) {
  return new State(c, out, out1);
}

// 辅助函数：连接指针列表
void patch(vector<State**> &l, State *s) {
  for (auto p : l) {
  *p = s;
  }
}

// 辅助函数：合并指针列表
vector<State**> append(const vector<State**> &l1, const vector<State**> &l2) {
  vector<State**> res = l1;
  res.insert(res.end(), l2.begin(), l2.end());
  return res;
}

// 将中缀正则转后缀 (Shunting-yard 简化版)
// 这里为了演示简单，假设输入已经是预处理好的，或者手动构造 NFA
// 实际实现通常需要一个 Parser

// 我们直接实现一个简单的后缀表达式构建器
Frag post2nfa(string postfix) {
  stack<Frag> stack;
  for (char c : postfix) {
  switch (c) {
  case '.': { // 连接
  Frag e2 = stack.top(); stack.pop();
  Frag e1 = stack.top(); stack.pop();
  patch(e1.out, e2.start);
  stack.push({e1.start, e2.out});
  break;
  }
  case '|': { // 并集
  Frag e2 = stack.top(); stack.pop();
  Frag e1 = stack.top(); stack.pop();
  State *s = state(256, e1.start, e2.start);
  stack.push({s, append(e1.out, e2.out)});
  break;
  }
  case '*': { // 闭包
  Frag e = stack.top(); stack.pop();
  State *s = state(256, e.start, nullptr); // split
  patch(e.out, s);
  stack.push({s, {&s->out1}});
  break;
  }
  default: { // 字符
  State *s = state(c, nullptr, nullptr);
  stack.push({s, {&s->out}});
  break;
  }
  }
  }
  Frag e = stack.top(); stack.pop();
  State *match = state(257, nullptr, nullptr);
  patch(e.out, match);
  return e;
}

// NFA 模拟
int listid = 0;
void addstate(vector<State*> &l, State *s) {
  if (s == nullptr || s->lastlist == listid) return;
  s->lastlist = listid;
  if (s->c == 256) { // split (epsilon)
  addstate(l, s->out);
  addstate(l, s->out1);
  } else {
  l.push_back(s);
  }
}

bool match(State *start, string s) {
  vector<State*> cList, nList;
  listid++;
  addstate(cList, start);
  
  for (char c : s) {
  listid++;
  nList.clear();
  for (State *st : cList) {
  if (st->c == c) {
  addstate(nList, st->out);
  }
  }
  cList = nList;
  }
  
  for (State *st : cList) {
  if (st->c == 257) return true;
  }
  return false;
}

int main() {
  // 构造 a(b|c)*d
  // 后缀表达式: abc|*.d.
  string postfix = "abc|*.d.";
  Frag nfa = post2nfa(postfix);
  
  cout << "Match abbbd: " << match(nfa.start, "abbbd") << endl;
  cout << "Match acd: " << match(nfa.start, "acd") << endl;
  cout << "Match ad: " << match(nfa.start, "ad") << endl;
  cout << "Match abd: " << match(nfa.start, "abd") << endl;
  cout << "Match abx: " << match(nfa.start, "abx") << endl;
  
  return 0;
}

NFA 转 DFA (子集构造法)

虽然 NFA 可以直接用于匹配，但它在运行时需要维护一个状态集合，并且频繁计算 \(\epsilon\)-闭包，这会带来性能开销。

如果我们能在编译阶段就把这些“状态集合”预先计算好，生成一个新的自动机，那么运行时只需要查表跳转，速度将大幅提升。 这个过程就是 NFA 到 DFA 的转换，通常使用 子集构造法 (Subset Construction)。

原理：状态集合即新状态

DFA 的每一个状态，实际上对应的是 NFA 的一个状态集合。 因为 NFA 在某一时刻可能处于 \(\{s_1, s_2, s_3\}\) 中的任意一个状态，对于 DFA 来说，\(\{s_1, s_2, s_3\}\) 这一整个集合就是一个确定的状态。

算法流程：

1. 初始状态：计算 NFA 起始节点的 \(\epsilon\)-闭包，作为 DFA 的起始状态 \(A\)。
2. 状态转移：对于 DFA 的每一个状态（即 NFA 的状态集合 \(S\)）和每一个输入字符 \(c\)：

• 找出 \(S\) 中所有节点经过 \(c\) 能到达的 NFA 节点集合 \(T\)。
• 计算 \(T\) 的 \(\epsilon\)-闭包，得到新的集合 \(U\)。
• 如果 \(U\) 是一个新的集合，就把它标记为 DFA 的一个新状态。
• 在 DFA 中添加一条从 \(S\) 到 \(U\) 的边，标记为 \(c\)。

3. 重复：直到没有新的 DFA 状态产生。
4. 结束状态：如果一个 DFA 状态代表的集合中包含 NFA 的结束节点，则该 DFA 状态为结束状态。

为什么 DFA 更快？

1. 消除运行时计算：NFA 匹配时，每读一个字符都要进行集合运算（并集、闭包）。DFA 匹配时，这些运算在编译期已经做完了。
2. O(1) 状态转移：DFA 的运行逻辑极其简单：current_state = transition_table[current_state][char]。这只是一个简单的数组索引操作。
3. 线性时间复杂度：

• NFA 匹配复杂度：\(O(m \times n)\)，其中 \(m\) 是正则长度（状态数），\(n\) 是文本长度。
• DFA 匹配复杂度：\(O(n)\)。速度与正则表达式的复杂程度无关！

加速效果与实例

加速多少？

在简单正则上，DFA 可能比 NFA 快 2-5 倍。但在复杂正则（特别是带有大量分支和循环）上，NFA 的状态集合会很大，DFA 的优势可以是 10 倍甚至 100 倍。 更重要的是，DFA 保证了最坏情况下的性能，不会因为构造了恶意的正则表达式而导致 ReDoS（正则表达式拒绝服务攻击）。

典型实例：

• grep / awk / lex：这些经典的 Unix 文本处理工具默认使用 DFA 引擎，因此处理海量日志时速度极快。
• RE2 (Google)：Go 语言的标准正则库。它坚持使用自动机理论（DFA/NFA 混合），放弃了反向引用等特性，换取了绝对的 \(O(n)\) 性能保证，被广泛用于高性能服务器。
• Rust regex：同样基于自动机，大量使用了 DFA 优化（如 Lazy DFA）。
• Hyperscan (Intel)：高性能正则匹配库，底层大量使用 DFA 和 SIMD 指令加速，用于网络包过滤（防火墙、IDS）。

DFA 完整代码实现

下面是一个基于子集构造法的 DFA 编译器实现。它将 NFA 转换为 DFA 状态转移表。

#include <map>
#include <algorithm>

// DFA 状态
struct DState {
  map<int, DState*> next; // 转移表: 字符 -> 下一个状态
  bool is_match;  // 是否为接受状态
  
  DState() : is_match(false) {}
};

// 辅助：比较两个 NFA 状态集合是否相同
// 这里的 set<State*> 是有序的，可以直接比较
typedef set<State*> StateSet;

// 全局缓存：NFA 状态集合 -> DFA 状态的映射
map<StateSet, DState*> dstate_cache;

// 计算 NFA 状态集合的 epsilon 闭包
StateSet epsilon_closure(const StateSet& start_states) {
  StateSet closure = start_states;
  stack<State*> worklist;
  for (State* s : start_states) worklist.push(s);
  
  while (!worklist.empty()) {
  State* s = worklist.top(); worklist.pop();
  
  // 检查 s 的 epsilon 边 (c == 256)
  if (s->c == 256) {
  if (s->out && closure.find(s->out) == closure.end()) {
  closure.insert(s->out);
  worklist.push(s->out);
  }
  if (s->out1 && closure.find(s->out1) == closure.end()) {
  closure.insert(s->out1);
  worklist.push(s->out1);
  }
  }
  }
  return closure;
}

// 获取或创建 DFA 状态
DState* get_dstate(StateSet states) {
  // 1. 计算闭包
  states = epsilon_closure(states);
  
  // 2. 查表，如果已存在则返回
  if (dstate_cache.count(states)) {
  return dstate_cache[states];
  }
  
  // 3. 创建新状态
  DState* d = new DState();
  dstate_cache[states] = d;
  
  // 检查是否包含 NFA 的接受状态 (257)
  for (State* s : states) {
  if (s->c == 257) {
  d->is_match = true;
  break;
  }
  }
  return d;
}

// 编译 NFA -> DFA
DState* compile_dfa(State* nfa_start) {
  dstate_cache.clear();
  
  // 初始状态
  StateSet start_set;
  start_set.insert(nfa_start);
  DState* dfa_start = get_dstate(start_set);
  
  // 待处理的 DFA 状态队列
  stack<DState*> worklist;
  worklist.push(dfa_start);
  
  // 已处理过的 DFA 状态集合 (避免重复处理)
  set<DState*> visited;
  visited.insert(dfa_start);
  
  while (!worklist.empty()) {
  DState* d = worklist.top(); worklist.pop();
  
  // 反向查找 d 对应的 NFA 状态集合 (为了演示简单，这里需要从 cache 中反查，
  // 实际实现中 DState 结构体里应该存一下对应的 StateSet)
  StateSet current_nfa_states;
  for (auto& pair : dstate_cache) {
  if (pair.second == d) {
  current_nfa_states = pair.first;
  break;
  }
  }
  
  // 找出所有可能的转移字符
  // 遍历当前集合中所有 NFA 节点，看它们能接受什么字符
  map<int, StateSet> transitions;
  for (State* s : current_nfa_states) {
  if (s->c < 256) { // 实际字符
  transitions[s->c].insert(s->out);
  }
  }
  
  // 对每个字符构建 DFA 边
  for (auto& pair : transitions) {
  int char_code = pair.first;
  StateSet next_nfa_states = pair.second;
  
  DState* next_dstate = get_dstate(next_nfa_states);
  d->next[char_code] = next_dstate;
  
  if (visited.find(next_dstate) == visited.end()) {
  visited.insert(next_dstate);
  worklist.push(next_dstate);
  }
  }
  }
  
  return dfa_start;
}

// DFA 匹配执行
bool dfa_match(DState* start, string s) {
  DState* curr = start;
  for (char c : s) {
  if (curr->next.count(c)) {
  curr = curr->next[c];
  } else {
  return false; // 无路可走，匹配失败
  }
  }
  return curr->is_match;
}

int main_dfa() {
  // 构造 a(b|c)*d
  string postfix = "abc|*.d.";
  Frag nfa = post2nfa(postfix);
  
  // 编译
  DState* dfa = compile_dfa(nfa.start);
  
  // 执行
  cout << "DFA Match abbbd: " << dfa_match(dfa, "abbbd") << endl;
  cout << "DFA Match acd: " << dfa_match(dfa, "acd") << endl;
  cout << "DFA Match ad: " << dfa_match(dfa, "ad") << endl;
  
  return 0;
}

DFA 与 NFA 的对比

• NFA 引擎：Perl, Python, Java, Ruby 等大多数语言的正则库。支持反向引用等高级特性，但可能出现回溯导致的性能问题（ReDoS）。
• DFA 引擎：awk, egrep, lex。速度极快，但不支持反向引用等特性。

Go 语言的 regexp 库使用的是 RE2 算法，它是一种混合方法，保证了 \(O(n)\) 的线性时间复杂度，避免了回溯爆炸。

RE2 算法与高性能正则

在工业界，正则表达式引擎的性能至关重要。传统的正则引擎（如 PCRE, Python re, Java Pattern）大多基于回溯（Backtracking）算法。虽然支持丰富的功能（如反向引用），但在某些情况下会出现指数级的时间复杂度，导致 ReDoS（正则表达式拒绝服务攻击）。

Google 的 RE2 算法正是为了解决这个问题而诞生的。它由 Russ Cox 开发，被 Go 语言标准库采用。

回溯引擎的缺陷 (The Problem)

回溯引擎本质上是一个深度优先搜索（DFS）。 考虑正则表达式 a?a?a?aaa 匹配字符串 aaaaa。 如果是 (a?){n}a{n} 匹配 a^{n}，回溯引擎的复杂度是 \(O(2^n)\)。

例如，对于正则 (x+x+)+y 匹配 xxxxxxxxxxxx... (没有 y)，回溯引擎会尝试所有的分割组合，导致死循环般的卡顿。

RE2 的原理 (The Solution)

RE2 的核心原则是：保证线性时间复杂度 \(O(n)\)，其中 \(n\) 是输入文本的长度。 它放弃了对“反向引用 (Backreferences)”和“零宽断言 (Lookaround)”等无法用有限自动机高效实现的功能的支持。

RE2 的实现策略是混合的：

1. 预编译：将正则解析为 NFA。
2. 执行策略：

• Bit-state hashing: 对于小模式串，使用位图记录状态。
• NFA Simulation: 使用 Thompson NFA 模拟（即前文提到的维护当前状态集合），复杂度 \(O(nm)\)。
• Lazy DFA: 这是 RE2 最快的部分。它不预先生成整个 DFA（因为状态可能爆炸），而是在匹配过程中按需生成 DFA 状态，并缓存起来。
• One-pass NFA: 对于需要提取子匹配（Capturing Groups）的情况，RE2 无法简单使用 DFA，而是使用一种优化的 NFA 模拟，同时记录路径信息。

Lazy DFA (惰性 DFA)

全量构建 DFA 可能会导致状态数量指数级膨胀（\(2^m\)）。 RE2 维护一个有限大小的 DFA 状态缓存。

1. 匹配开始时，缓存为空。
2. 每读入一个字符，计算目标状态。
3. 如果目标状态已经在缓存中，直接跳转。
4. 如果不在，利用 NFA 计算出目标状态集合，存入缓存。
5. 如果缓存满了，直接清空或丢弃部分，或者回退到 NFA 模拟。

这种方式结合了 DFA 的速度（大部分时间查表 \(O(1)\)）和 NFA 的空间安全性。

核心代码逻辑演示

RE2 的实际代码非常复杂（C++），包含内存管理和各种优化。这里展示其核心的 Lock-step NFA Simulation 思想，这是它区别于回溯引擎的关键。

// 这是一个简化的 Go 语言描述，展示 RE2 如何避免回溯
// 假设我们已经有了 NFA 图

type State struct {
  char int // 匹配字符
  out  *State
  out1 *State // 用于 split
}

func Match(start *State, text string) bool {
  // 当前活跃的状态集合
  // 使用 map 或 dense array 去重
  clist := make(map[*State]bool)
  nlist := make(map[*State]bool)
  
  addState(clist, start) // 初始状态及其 epsilon 闭包
  
  for _, char := range text {
  // 这一步是关键：同时推演所有可能的状态
  // 而不是像回溯引擎那样一条路走到黑
  nlist = make(map[*State]bool)
  
  for s := range clist {
  if s.char == char {
  addState(nlist, s.out)
  }
  }
  
  clist = nlist
  if len(clist) == 0 {
  return false // 提前结束
  }
  }
  
  // 检查是否包含接受状态
  for s := range clist {
  if s.char == MatchState {
  return true
  }
  }
  return false
}

// 辅助：添加状态并处理 epsilon 转换
func addState(l map[*State]bool, s *State) {
  if s == nil || l[s] {
  return
  }
  if s.char == Split { // Epsilon
  addState(l, s.out)
  addState(l, s.out1)
  return
  }
  l[s] = true
}

总结

常见正则表达式实例

理解了原理之后，我们来看几个实际开发中常用的正则表达式例子。

1. 电子邮箱 (Email)

^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$

• ^ 和 $: 匹配整个字符串的开始和结束。
• [a-zA-Z0-9._%+-]+: 用户名部分，允许字母、数字和一些特殊符号，至少出现一次。
• @: 必须包含 @ 符号。
• [a-zA-Z0-9.-]+: 域名主体。
• \.: 匹配点号。
• [a-zA-Z]{2,}: 顶级域名（如 com, org, cn），至少 2 个字母。

2. IPv4 地址

^(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)$

这是一个比较严谨的匹配，考虑了数字范围 0-255。

• (?:...): 非捕获组，只分组不捕获。
• 25[0-5]: 匹配 250-255。
• 2[0-4][0-9]: 匹配 200-249。
• [01]?[0-9][0-9]?: 匹配 0-199 (包括 0-9, 00-99)。
• {3}: 前面三段加点号重复 3 次。

3. 日期 (YYYY-MM-DD)

^\d{4}-(?:0[1-9]|1[0-2])-(?:0[1-9]|[12]\d|3[01])$

• \d{4}: 4 位年份。
• 0[1-9]|1[0-2]: 月份 01-12。
• 0[1-9]|[12]\d|3[01]: 日期 01-31。

4. 手机号码 (中国大陆)

^1[3-9]\d{9}$

• 1: 以 1 开头。
• [3-9]: 第二位通常是 3-9。
• \d{9}: 后面跟着 9 位数字。

5. 简单的 HTML 标签

<([a-z]+)([^<]+)*(?:>(.*)<\/\1>|\s+\/>)

• ([a-z]+): 捕获标签名 (如 div, span)。
• (?:>(.*)<\/\1>|\s+\/>): 匹配闭合标签 >...</div> 或自闭合标签 />。
• \1: 反向引用第一个捕获组（标签名），确保首尾标签一致。 (注意：RE2 等纯自动机引擎不支持 \1 反向引用，这个例子仅适用于支持回溯的引擎)

正则表达式的能力边界

虽然正则表达式非常强大，但它并不是万能的。在计算理论中，正则表达式对应的是有限自动机 (Finite Automaton)。顾名思义，它的核心限制在于“有限”的内存（状态）。

哪些可以匹配？ (正则语言)

只要一个问题只需要有限的内存来记录当前的状态，它通常就可以用正则表达式解决。

1. 固定模式：如关键词查找 hello。
2. 有限的重复：如 a{5} (5个a)。
3. 不确定的重复：如 a* (任意个a)。
4. 有限的选择：如 a|b。
5. 有限长度的上下文：如“后面跟着数字的字母”。

哪些不能匹配？ (非正则语言)

如果一个问题需要无限的内存（或者说，内存的大小与输入长度相关），那么它就超出了正则表达式的能力范围。

最典型的例子是：任意深度的嵌套结构。

1. 配对的括号：\(L = \{ a^n b^n \mid n \ge 1 \}\)，即 ab, aabb, aaabbb…

• 为了匹配这个，机器需要“记住”读了多少个 a，以便检查后面是否有相同数量的 b。
• 因为 \(n\) 可以是无穷大，有限自动机没有足够的“状态”来计数。
• 注：这是上下文无关语言 (Context-Free Language) 的范畴，需要下推自动机 (Pushdown Automaton, 带栈的自动机)。

2. 回文串：\(L = \{ w w^R \mid w \in \{a,b\}^* \}\)，如 abba, baab。

• 同样需要记忆前半段的内容，长度不限，有限状态机无法做到。

3. 算术表达式：如 ((1+2)*3)，因为涉及任意深度的括号嵌套。

4. HTML/XML 解析：虽然可以用正则匹配简单的 <div>...</div>，但无法处理嵌套的 <div><div>...</div></div>。

判断标准：泵引理 (Pumping Lemma)

如何从理论上严格证明一个语言不是正则语言？我们使用泵引理。

定理描述：

如果语言 \(L\) 是正则语言，那么存在一个常数 \(p\)（泵长度），使得 \(L\) 中任何长度至少为 \(p\) 的字符串 \(s\) 都可以被分割成三部分 \(s = xyz\)，满足：

1. \(|y| > 0\) （中间部分不为空）

2. \(|xy| \le p\) （前两部分长度不超过 \(p\)）

3. 对于任意 \(k \ge 0\)，字符串 \(xy^k z\) 仍属于 \(L\) （中间部分 \(y\) 可以重复任意次——即“泵出”——结果仍在语言中）。

直观理解 (鸽巢原理)：

想象一个有限自动机（DFA）有 \(p\) 个状态。 如果你给它一个长度为 \(p\)（或更长）的字符串，它在处理过程中必须经过 \(p+1\) 次状态转移（包括起始状态）。 根据鸽巢原理，既然只有 \(p\) 个状态，但走了 \(p+1\) 步，那么必然至少有一个状态被访问了两次。

这就意味着路径中出现了一个环 (Loop)。

我们可以把字符串 \(s\) 的路径分为三段：

1. \(x\)：从起始状态走到第一次进入该重复状态的路径。

2. \(y\)：从该重复状态出发，转了一圈又回到该状态的路径（即“环”）。

3. \(z\)：从该重复状态继续走到结束状态的路径。

因为 \(y\) 是一个环，我们可以选择：

• 不走这个环 (\(k=0\), 也就是 \(xz\))
• 走一次 (\(k=1\), 也就是 \(xyz\))
• 走多次 (\(k=2, 3...\), 也就是 \(xyyz, xyyyz...\))

无论走多少次，自动机最终都会到达同一个接受状态。这就是“泵出”的含义。

证明实例：\(L = \{ a^n b^n \}\) 不是正则语言

为了证明 \(L = \{ a^n b^n \mid n \ge 0 \}\)（即 \(n\) 个 \(a\) 后面跟着 \(n\) 个 \(b\)）不是正则语言，我们使用反证法。

1. 假设与取值

步骤：假设 \(L\) 是正则语言。根据泵引理，必然存在一个泵长度 \(p\)。

解释：这就好比说，如果这个语言能被一个有限状态机识别，那么这个机器一定有 \(p\) 个状态。

步骤：我们构造一个特定的字符串 \(s = a^p b^p\)。

解释：这个字符串显然属于 \(L\)（\(a\) 和 \(b\) 数量相等），而且它的长度 \(2p\) 肯定大于 \(p\)。我们选这个字符串是为了“刁难”这个自动机。

2. 分割字符串

步骤：根据引理，字符串 \(s\) 必然可以被分割成三部分 \(s = xyz\)，并且满足两个关键条件： 1. \(|xy| \le p\) （前两部分长度不超过 \(p\)） 2. \(|y| > 0\) （中间部分 \(y\) 不能为空）

解释： 我们的字符串 \(s\) 长这样： \[ \underbrace{a a \dots a}_{p \text{个}} \underbrace{b b \dots b}_{p \text{个}} \]

因为限制了 \(|xy| \le p\)，这意味着 \(x\)和 \(y\) 完全落在前 \(p\) 个字符的范围内。 而前 \(p\) 个字符全都是 \(a\)。 结论：\(y\) 必然完全由 \(a\) 组成。

3. “泵出”产生矛盾 (Pumping)

步骤：根据引理，如果我们把中间部分 \(y\) 重复一次（即 \(xy^2z\)），得到的新字符串也应该属于 \(L\)。

具体演示： 设 \(y\) 的长度为 \(k\)（\(k \ge 1\)）。因为 \(y\) 全是 \(a\)，所以 \(y = a^k\)。

• 原字符串 \(s = xyz\)：包含 \(p\) 个 \(a\) 和 \(p\) 个 \(b\)。
• 泵出后的字符串 \(s' = x y y z\)：
• 我们在中间多插入了一个 \(y\)。
• 因为 \(y\) 全是 \(a\)，所以 \(a\) 的数量增加了 \(k\) 个。
• \(b\) 的部分完全在 \(z\) 里，没有变动。
• 结果：\(s'\) 包含 \(p+k\) 个 \(a\) 和 \(p\) 个 \(b\)。

4. 结论

步骤：检查 \(s'\) 是否属于 \(L\)。

解释： \(L\) 的定义要求 \(a\) 和 \(b\) 的数量必须严格相等。 但在 \(s'\) 中，\(a\) 的数量 (\(p+k\)) 显然不等于 \(b\) 的数量 (\(p\))，因为 \(k \ge 1\)。 所以 \(s' \notin L\)。

这与泵引理的结论（\(s'\) 必须属于 \(L\)）矛盾！ 因此，最开始的假设（\(L\) 是正则语言）是错误的。

提示：举个具体的数字例子

如果上面的符号太抽象，我们设泵长度 \(p = 3\)。

1. 构造字符串：选 \(s = a^3 b^3 = \text{aaabbb}\)。
2. 尝试分割：我们要把 \(\text{aaabbb}\) 分成 \(x, y, z\)，且 \(|xy| \le 3\)，\(|y| \ge 1\)。 因为 \(|xy| \le 3\)，所以 \(x\) and \(y\) 只能在前 3 个字符 aaa 里面切。

情况 A：\(x=\epsilon, y=a, z=aabbb\) - \(y\) 是 a。 - 泵出（重复 \(y\)）：\(x \cdot y \cdot y \cdot z = \epsilon \cdot a \cdot a \cdot aabbb = \text{aaaabbb}\)。 - 结果：4 个 \(a\)，3 个 \(b\)。不匹配！

情况 B：\(x=a, y=aa, z=bbb\) - \(y\) 是 aa。 - 泵出：\(x \cdot y \cdot y \cdot z = a \cdot aa \cdot aa \cdot bbb = \text{aaaaabbb}\)。 - 结果：5 个 \(a\)，3 个 \(b\)。不匹配！

无论怎么切，只要 \(y\) 在前 \(p\) 个字符里（全是 \(a\)），重复 \(y\) 就会导致 \(a\) 变多，\(b\) 不变，从而破坏数量平衡。 这就是为什么有限自动机无法识别 \(a^n b^n\) —— 它数不清 \(a\) 有多少个，也就无法确保后面有相同数量的 \(b\)。

结论

• 能用正则：词法分析（Token识别）、简单的格式校验（邮箱、日期）、扁平的文本搜索。
• 不能用正则：语法分析（解析代码结构）、处理嵌套括号、解析 HTML/XML/JSON。

对于嵌套结构，请使用解析器 (Parser)，不要试图用正则表达式去“强行”匹配。