不确定有限自动机 (NFA)

学习目标

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

• 理解NFA与DFA的区别
• 掌握ε转移的概念
• 认识NFA的例子
• 理解NFA的形式化定义

1. NFA 与 DFA 的区别

1.1 核心区别

DFA (确定有限自动机)：
- 对于每个状态和每个输入符号，只有一个下一状态
- 没有 ε 转移
- 确定性：不存在歧义

NFA (不确定有限自动机)：
- 对于每个状态和每个输入符号，可以有零个或多个下一状态
- 可以有 ε 转移（不需要输入就能转移）
- 不确定性：可能存在多种选择

1.2 形象对比

DFA 就像一个人在迷宫中走路：
- 每个岔路口只有一条路
- 每一步都必须有人指引（输入）

NFA 就像一个人可以分裂成多个副本在迷宫中走路：
- 每个岔路口可以有多个选择
- 可以凭空传送到其他位置（ε转移）
- 只要有一个副本到达终点就算成功

2. ε 转移

2.1 什么是 ε 转移？

ε 转移（空转移）是指不需要输入任何字符就能进行的状态转移。

ε 转移的表示：
在状态图中，用 ε 作为箭头上的标签

例子：
┌───┐   ε   ┌───┐
│ q0│──────→│ q1│
└───┘       └───┘

这个转移表示从 q0 到 q1 不需要任何输入

2.2 ε 转移的作用

ε 转移的好处：
1. 简化自动机的设计
2. 更容易从正则表达式构造自动机
3. 可以表达更复杂的语言结构

例子：
识别 "a" 或 "b" 的 NFA：
      ┌───┐
      │ ε │
      └─┬─┘
        │
        ▼
┌───┐  ┌───┐  ┌───┐
│ q0│──→│ q1│──→│ q2│
└───┘  └───┘  └───┘
  │      │ a    │ε
  │      │      │
  │      │      ▼
  │ ε    │  ┌───┐
  └──┐   │  │ q3│
     │   │  └───┘
     ▼   │     ↑
┌───┐     │     │
│ q4│──┐  │     │
└───┘  │  │     │
       │  │     │ b
       ▼  ▼     │
      ┌───┐     │
      │ q5│─────┘
      └───┘

3. NFA 的形式化定义

3.1 NFA 的定义

NFA = (Q, Σ, δ, q0, F)

其中：
Q: 有限状态集合
Σ: 输入字母表
δ: 状态转换函数 δ: Q × (Σ ∪ {ε}) → P(Q)
   P(Q) 是 Q 的幂集（所有子集的集合）
q0: 开始状态，q0 ∈ Q
F: 接受状态集合，F ⊆ Q

3.2 与 DFA 的对比

4. NFA 的例子

4.1 示例 1：识别包含 "a" 或 "b" 的字符串

NFA 设计：
状态：q0, q1, q2, q3, q4, q5
接受状态：q3

状态图：

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

转移函数：
δ(q0, ε) = {q1, q4}
δ(q1, a) = {q2}
δ(q2, ε) = {q3}
δ(q4, ε) = {q5}
δ(q5, b) = {q3}

4.2 示例 2：识别以 "ab" 或 "ba" 结尾的字符串

NFA 设计：
状态：q0, q1, q2, q3, q4
接受状态：q3, q4

状态图：

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

转移函数：
δ(q0, ε) = {q1, q2}
δ(q1, a) = {q1, q3}
δ(q3, b) = {q3}
δ(q2, b) = {q2, q4}
δ(q4, a) = {q4}

5. NFA 的工作原理

5.1 处理字符串的过程

NFA 处理字符串的过程：
1. 从开始状态出发，应用所有可能的 ε 转移，得到初始状态集合
2. 对于字符串中的每个字符：
   a. 对于当前状态集合中的每个状态，应用该输入字符的所有可能转移
   b. 对于每个得到的状态，再应用所有可能的 ε 转移
   c. 合并所有可能的状态，得到新的状态集合
3. 处理完所有字符后：
   a. 如果最终状态集合中包含至少一个接受状态 → 接受
   b. 否则 → 拒绝

5.2 示例运行

示例：用 NFA 识别 "a"

NFA 状态图：
      ┌───┐
      │ ε │
      └─┬─┘
        │
        ▼
┌───┐  ┌───┐  ┌───┐
│ q0│──→│ q1│──→│ q2│
└───┘  └───┘  └───┘
  │      │ a    │ε
  │      │      │
  │      │      ▼
  │ ε    │  ┌───┐
  └──┐   │  │ q3│
     │   │  └───┘
     ▼   │     ↑
┌───┐     │     │
│ q4│──┐  │     │ b
       │  │     │
       ▼  ▼     │
      ┌───┐     │
      │ q5│─────┘
      └───┘

输入 "a" 的处理过程：
1. 初始状态集合：
   - q0 应用 ε 转移 → {q1, q4}
   - 所以初始状态集合 S0 = {q1, q4}

2. 处理输入 'a'：
   - 对于 q1，输入 'a' → {q2}
   - 对于 q4，输入 'a' → ∅
   - 合并得到 {q2}
   - 对 q2 应用 ε 转移 → {q3}
   - 所以新的状态集合 S1 = {q3}

3. 处理完所有字符，检查 S1：
   - S1 = {q3}，q3 是接受状态
   - 结果：接受 ✓

6. 实用案例

6.1 案例 1：用 Python 实现 NFA

class NFA:
    def __init__(self, states, alphabet, transitions, start_state, accept_states):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.start_state = start_state
        self.accept_states = accept_states
    
    def epsilon_closure(self, states):
        """计算状态集合的 ε-闭包"""
        stack = list(states)
        closure = set(states)
        
        while stack:
            state = stack.pop()
            if state in self.transitions and 'ε' in self.transitions[state]:
                for next_state in self.transitions[state]['ε']:
                    if next_state not in closure:
                        closure.add(next_state)
                        stack.append(next_state)
        return closure
    
    def move(self, states, symbol):
        """对于状态集合和输入符号，计算下一状态集合"""
        next_states = set()
        for state in states:
            if state in self.transitions and symbol in self.transitions[state]:
                next_states.update(self.transitions[state][symbol])
        return next_states
    
    def accepts(self, string):
        """判断字符串是否被接受"""
        # 计算初始状态的 ε-闭包
        current_states = self.epsilon_closure({self.start_state})
        
        for symbol in string:
            # 应用输入符号
            current_states = self.move(current_states, symbol)
            # 计算 ε-闭包
            current_states = self.epsilon_closure(current_states)
            # 如果没有状态了，直接拒绝
            if not current_states:
                return False
        
        # 检查是否有接受状态
        return any(state in self.accept_states for state in current_states)

# 创建识别 "a" 或 "b" 的 NFA
states = {'q0', 'q1', 'q2', 'q3', 'q4', 'q5'}
alphabet = {'a', 'b'}
transitions = {
    'q0': {'ε': {'q1', 'q4'}},
    'q1': {'a': {'q2'}},
    'q2': {'ε': {'q3'}},
    'q4': {'ε': {'q5'}},
    'q5': {'b': {'q3'}}
}
start_state = 'q0'
accept_states = {'q3'}

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

# 测试
print(nfa.accepts('a'))    # True
print(nfa.accepts('b'))    # True
print(nfa.accepts('ab'))   # True
print(nfa.accepts('c'))    # False
print(nfa.accepts(''))     # False (空字符串)

6.2 案例 2：识别 "a*b" 的 NFA

# 识别 "a*b" 的 NFA
states = {'q0', 'q1', 'q2'}
alphabet = {'a', 'b'}
transitions = {
    'q0': {'ε': {'q1'}},
    'q1': {'a': {'q1'}, 'ε': {'q2'}},
    'q2': {'b': {'q2'}}
}
start_state = 'q0'
accept_states = {'q2'}

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
print(nfa.accepts(''))     # False

7. 自测问题

1. NFA 与 DFA 的主要区别是什么？
2. 什么是 ε 转移？
3. NFA 的形式化定义是什么？
4. NFA 如何处理一个字符串？
5. NFA 和 DFA 的表达能力是否相同？为什么？

8. 下集预告

下一集我们将学习从正则表达式到 NFA 的转换！

参考资料

• 《编译原理》（龙书）
• 《自动机理论、语言和计算导论》