01-有限自动机&正则文法

基础概念

Alphabet: $\Sigma$ ，有限的字符集合
String: 由 $\Sigma$ 中的字符组成的有限序列
- 空串: $\epsilon$ ，长度为0的字符串
- 子串
- 前缀/后缀
字符串运算
- Concatenation: $w_1 w_2$ ， $w_1$ 和 $w_2$ 的连接
- Reverse: $w^R$ ，字符串的逆序
- Length: $|w|$ ，字符串的长度
- Power: $w^n$ ，字符串的重复， $w^0 = \epsilon$
Language: 字符串的集合
- Kleene star: $\Sigma^*$ ，字母表 $\Sigma$ 上的所有字符串的集合
- Plus: $\Sigma^+$ ，字母表 $\Sigma$ 上的所有非空字符串的集合
- Language 是 $\Sigma^*$ 的非空子集（可以为 $\{\epsilon\}$ ）
语言运算
- 交并减补
- Reverse： $L^R = \{w^R | w \in L\}$
- Concatenation： $L_1 L_2 = \{w_1 w_2 | w_1 \in L_1, w_2 \in L_2\}$
- Power： $L^n = \{w_1 w_2 \cdots w_n | w_i \in L\}$
- Star-closure： $L^* = \bigcup_{i=0}^{\infty} L^i$
- Positive-closure： $L^+ = \bigcup_{i=1}^{\infty} L^i= L^* - \{\epsilon\}$

例题

$L_= \{a, b\}, L^3 = \{aaa, aab, aba, abb, baa, bab, bba, bbb\}$ $L_= \{a^nb^n:n \ge 0\}, L^2 = \{a^nb^n a^mb^m: n, m \ge 0\}$

Bi-Simulation：两个状态的输入输出行为相同，两个 DFA 是等价的
判断步骤
1. 找到两个 DFA 的初始状态作为待检查的状态
2. 对于每一个输入，找到待检查状态转移后的状态，将其加入待检查状态
3. 重复 2 ，直到没有新的状态被加入
4. 所有状态对中，如果两个状态同时为终止状态或同时为非终止状态，则两个 DFA 是等价的

对于一个输入字符，可以有多个状态转移，只要有一个状态转移成功，就可以接受
允许 $\epsilon$ 转移
定义
- $M = (Q, \Sigma \cup \{\epsilon\}, \delta, q_0, F)$
- $\delta: Q \times (\Sigma \cup \{\epsilon\}) \mapsto 2^Q$ ( $2^Q$ 表示 $Q$ 的幂集，所有的子集)
$\epsilon \text{-closure} (q)$ ：从状态 $q$ 开始，所有通过 $\epsilon$ 转移，不消耗其他字符可以到达的状态的集合
- $q \in \epsilon \text{-closure} (q)$
- 状态转移的拓展：匹配完成后，如果还能通过 $\epsilon$ 转移到达其他状态，则将这些状态也加入
  - $\delta^*: Q \times \Sigma^* \mapsto 2^Q$
  - $\delta^*(q, w) = \bigcup_{q' \in \delta^*(q, a)} \epsilon \text{-closure} (q')$
- 使用 NFA 定义语言： $L(M) = \{w \in \Sigma^* | \delta^*(q_0, w) \cap F \neq \emptyset\}$

DFA 显然是 NFA 的特例
NFA 可以转换为 DFA
转换步骤：子集构造法
1. 初始化 DFA 的初始状态集合为 $S_0=\epsilon \text{-closure} (q_0)$
2. 对于每一个输入字符 $a$ ，找到所有能到达的转移状态的集合 $S' = \bigcup_{q \in S} \delta(q, a)$
3. 将 $S''=\epsilon \text{-closure} (S')$ 加入 DFA 的状态集合，如果转移状态中包含 NFA 的 Final 状态，则加入 DFA 的 Final 状态集合
4. 重复，直到所有状态都被加入
最差时间复杂度： $\Theta(2^n)$

当 NFA 转换为 DFA 时，规模不一定会减小

最后更新于1个月前