从正则表达式到 NFA

学习目标

通过本集的学习，你将能够：

  • 掌握 Thompson 构造法
  • 理解基本构造块
  • 学会组合操作
  • 完成示例演练

1. Thompson 构造法

1.1 什么是 Thompson 构造法？

Thompson 构造法是一种从正则表达式自动构造 NFA 的算法，由 Kenneth Thompson 在 1968 年提出。

Thompson 构造法的特点：
- 递归地从正则表达式的子表达式构造 NFA
- 使用 ε 转移来组合不同的子表达式
- 构造出的 NFA 状态数与正则表达式长度成线性关系
- 构造过程简单且高效

1.2 构造过程

构造步骤：
1. 对于基本符号（单个字符），构造基本的 NFA
2. 对于组合操作（连接、选择、重复），使用 ε 转移组合子 NFA
3. 递归地处理所有子表达式
4. 最终得到整个正则表达式的 NFA

2. 基本构造块

2.1 空字符串 ε

正则表达式：ε

构造的 NFA：

┌───┐   ε   ┌───┐
│ q0│──────→│ q1│
└───┘       └───┘

状态：q0（开始），q1（接受）

2.2 单个字符 a

正则表达式：a

构造的 NFA：

┌───┐   a   ┌───┐
│ q0│──────→│ q1│
└───┘       └───┘

状态：q0（开始），q1（接受）

2.3 空集 ∅

正则表达式：∅（匹配空集，不匹配任何字符串）

构造的 NFA：

┌───┐
│ q0│
└───┘

状态：q0（开始，没有接受状态）

3. 组合操作

3.1 连接操作（AB）

正则表达式：AB（先匹配 A，再匹配 B）

构造方法：
1. 构造 A 的 NFA：N_A
2. 构造 B 的 NFA：N_B
3. 将 N_A 的接受状态与 N_B 的开始状态用 ε 转移连接
4. 新的开始状态是 N_A 的开始状态
5. 新的接受状态是 N_B 的接受状态

图示：

N_A 的 NFA：  N_B 的 NFA：
┌───┐   A   ┌───┐   ┌───┐   B   ┌───┐
│ q0│──────→│ q1│   │ q2│──────→│ q3│
└───┘       └───┘   └───┘       └───┘

连接后的 NFA：
┌───┐   A   ┌───┐   ε   ┌───┐   B   ┌───┐
│ q0│──────→│ q1│──────→│ q2│──────→│ q3│
└───┘       └───┘       └───┘       └───┘

3.2 选择操作（A|B）

正则表达式：A|B（匹配 A 或 B）

构造方法：
1. 构造 A 的 NFA：N_A
2. 构造 B 的 NFA：N_B
3. 创建新的开始状态 q0
4. 创建新的接受状态 qf
5. 从 q0 到 N_A 的开始状态添加 ε 转移
6. 从 q0 到 N_B 的开始状态添加 ε 转移
7. 从 N_A 的接受状态到 qf 添加 ε 转移
8. 从 N_B 的接受状态到 qf 添加 ε 转移

图示：
      ┌───┐
      │ ε │
      └─┬─┘
        │
        ▼
┌───┐  ┌───┐  ┌───┐
│ q0│─→│ q1│─→│ q2│
└───┘  └───┘  └───┘
  │      │A     │ε
  │      │      │
  │      │      ▼
  │ ε    │  ┌───┐
  └──┐   │  │ qf│
     │   │  └───┘
     ▼   │     ↑
┌───┐     │     │
│ q3│─┐  │     │
└───┘  │  │     │ B
       │  │     │
       ▼  ▼     │
      ┌───┐     │
      │ q4│─────┘
      └───┘

3.3 重复操作（A*）

正则表达式：A*（匹配 A 零次或多次）

构造方法：
1. 构造 A 的 NFA：N_A
2. 创建新的开始状态 q0
3. 创建新的接受状态 qf
4. 从 q0 到 N_A 的开始状态添加 ε 转移
5. 从 N_A 的接受状态到 N_A 的开始状态添加 ε 转移（循环）
6. 从 N_A 的接受状态到 qf 添加 ε 转移
7. 从 q0 到 qf 添加 ε 转移（匹配零次）

图示：
      ┌───┐
      │ ε │
      └─┬─┘
        │
        ▼
┌───┐  ┌───┐  ┌───┐
│ q0│─→│ q1│─→│ q2│
└───┘  └───┘  └───┘
  │      │A     │ε
  │      │      │
  │      │      ▼
  │ ε    │  ┌───┐
  └──┐   │  │ qf│
     │   │  └───┘
     │   │     ↑
     │   └─────┘ ε
     │         │
     └─────────┘ ε

3.4 正闭包（A+）

正则表达式：A+（匹配 A 一次或多次）

构造方法：
1. 等价于 AA*
2. 构造 A 的 NFA：N_A
3. 构造 A* 的 NFA：N_A*
4. 连接 N_A 和 N_A*

图示：

┌───┐   A   ┌───┐   ε   ┌───┐  ┌───┐  ┌───┐
│ q0│──────→│ q1│──────→│ q2│─→│ q3│─→│ q4│
└───┘       └───┘       └───┘  └───┘  └───┘
                  │      │A     │ε
                  │      │      │
                  │      │      ▼
                  │ ε    │  ┌───┐
                  └──┐   │  │ q5│
                     │   │  └───┘
                     │   │     ↑
                     │   └─────┘ ε
                     │         │
                     └─────────┘ ε

3.5 可选（A?）

正则表达式：A?（匹配 A 零次或一次）

构造方法：
1. 等价于 ε|A
2. 使用选择操作构造

图示：
      ┌───┐
      │ ε │
      └─┬─┘
        │
        ▼
┌───┐  ┌───┐  ┌───┐
│ q0│─→│ q1│─→│ q2│
└───┘  └───┘  └───┘
  │      │A     │ε
  │      │      │
  │      │      ▼
  │ ε    │  ┌───┐
  └──┐   │  │ q3│
     │   │  └───┘
     │   │     ↑
     │   └─────┘ ε
     │         │
     └─────────┘ ε

4. 示例演练

4.1 示例 1：正则表达式 a|b

构造步骤：
1. 构造 a 的 NFA：
   ┌───┐   a   ┌───┐
   │ q1│──────→│ q2│
   └───┘       └───┘

2. 构造 b 的 NFA：
   ┌───┐   b   ┌───┐
   │ q3│──────→│ q4│
   └───┘       └───┘

3. 应用选择操作：
   - 创建新开始状态 q0
   - 创建新接受状态 q5
   - 添加 ε 转移：q0→q1, q0→q3, q2→q5, q4→q5

最终 NFA：

      ┌───┐
      │ ε │
      └─┬─┘
        │
        ▼
┌───┐  ┌───┐  ┌───┐
│ q0│─→│ q1│─→│ q2│
└───┘  └───┘  └───┘
  │      │a     │ε
  │      │      │
  │      │      ▼
  │ ε    │  ┌───┐
  └──┐   │  │ q5│
     │   │  └───┘
     ▼   │     ↑
┌───┐     │     │
│ q3│─┐  │     │ b
       │  │     │
       ▼  ▼     │
      ┌───┐     │
      │ q4│─────┘
      └───┘

4.2 示例 2：正则表达式 ab*c

构造步骤：
1. 构造 a 的 NFA：N_a
2. 构造 b* 的 NFA：N_b*
3. 构造 c 的 NFA：N_c
4. 连接 N_a, N_b*, N_c

最终 NFA：

┌───┐   a   ┌───┐   ε   ┌───┐  ┌───┐  ┌───┐   ε   ┌───┐   c   ┌───┐
│ q0│──────→│ q1│──────→│ q2│─→│ q3│─→│ q4│──────→│ q5│──────→│ q6│
└───┘       └───┘       └───┘  └───┘  └───┘       └───┘       └───┘
                  │      │b     │ε
                  │      │      │
                  │      │      ▼
                  │ ε    │  ┌───┐
                  └──┐   │  │ q7│
                     │   │  └───┘
                     │   │     ↑
                     │   └─────┘ ε
                     │         │
                     └─────────┘ ε

4.3 示例 3：正则表达式 (a|b)*c

构造步骤：
1. 构造 (a|b) 的 NFA：N_choice
2. 构造 N_choice* 的 NFA：N_star
3. 构造 c 的 NFA：N_c
4. 连接 N_star 和 N_c

最终 NFA：

      ┌───┐
      │ ε │
      └─┬─┘
        │
        ▼
┌───┐  ┌───┐  ┌───┐  ┌───┐  ┌───┐   ε   ┌───┐   c   ┌───┐
│ q0│─→│ q1│─→│ q2│─→│ q3│─→│ q4│──────→│ q5│──────→│ q6│
└───┘  └───┘  └───┘  └───┘  └───┘       └───┘       └───┘
  │      │ε     │a     │ε
  │      │      │      │
  │      │      │      ▼
  │ ε    │      │  ┌───┐
  └──┐   │      │  │ q7│
     │   │      │  └───┘
     │   │ ε    │     ↑
     │   └─┐    │     │
     │     │    │     │
     ▼     ▼    │     │ ε
┌───┐  ┌───┐    │     │
│ q8│─→│ q9│────┘     │
└───┘  └───┘           │
         │b            │
         │             │
         └─────────────┘

4. 实用案例

4.1 案例 1：构造正则表达式 a*b 的 NFA

# 使用前面的 NFA 类
states = {
    'q0', 'q1', 'q2', 'q3'  # q0:开始, q3:接受
}
alphabet = {'a', 'b'}
transitions = {
    'q0': {'ε': {'q1', 'q3'}},
    'q1': {'a': {'q2'}},
    'q2': {'ε': {'q1', 'q3'}}
}
start_state = 'q0'
accept_states = {'q3'}

nfa = NFA(states, alphabet, transitions, start_state, accept_states)

# 测试
print(nfa.accepts('b'))    # True
print(nfa.accepts('ab'))   # True
print(nfa.accepts('aab'))  # True
print(nfa.accepts('aa'))   # False

4.2 案例 2：构造正则表达式 (a|b)* 的 NFA

states = {
    'q0', 'q1', 'q2', 'q3', 'q4', 'q5', 'q6'  # q0:开始, q6:接受
}
alphabet = {'a', 'b'}
transitions = {
    'q0': {'ε': {'q1', 'q6'}},
    'q1': {'ε': {'q2', 'q4'}},
    'q2': {'a': {'q3'}},
    'q3': {'ε': {'q5'}},
    'q4': {'b': {'q5'}},
    'q5': {'ε': {'q1', 'q6'}}
}
start_state = 'q0'
accept_states = {'q6'}

nfa = NFA(states, alphabet, transitions, start_state, accept_states)

# 测试
print(nfa.accepts(''))     # True
print(nfa.accepts('a'))    # True
print(nfa.accepts('b'))    # True
print(nfa.accepts('ab'))   # True
print(nfa.accepts('aba'))  # True

5. 自测问题

  1. 什么是 Thompson 构造法？
  2. 基本构造块有哪些？
  3. 连接操作如何构造 NFA？
  4. 选择操作如何构造 NFA？
  5. 重复操作如何构造 NFA？

6. 下集预告

下一集我们将学习 NFA 到 DFA 的转换！

参考资料

  • 《编译原理》（龙书）
  • 《自动机理论、语言和计算导论》
  • Thompson, K. (1968). "Regular Expression Search Algorithm"
« 上一篇 不确定有限自动机 (NFA) 下一篇 » NFA 到 DFA 的转换
↑