复习材料，不建议阅读

词法分析

形式化描述工具（基础概念）

正规文法

也就是 3 型文法，大家都知道。也就是左边一个非终结符号，右边只能最右出现非终结符号。

正规式

也叫正则表达式，这里不多赘述。只能描述正规语言，不能描述上下文相关的语言。

它和正规文法的等价描述可以相互转换。

有穷自动机

确定有穷自动机 DFA

一个确定的有穷自动机 MM 是一个五元组:

M=(K,∑,f,S,Z)M = ( K , \sum , f , S , Z )

其中:

  1. KK 是一个有穷集，它的每个元素称为一个状态。
  2. ∑\sum 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表。
  3. ff 是转换函数，是 K×E→KK \times E \to K 上的映像。例如， f(ki,a)=kj(ki∈K,kj∈K)f(k_i, a)=k_j (k_i \in K, k_j \in K)，就意味着，当前状态为 kik_i、输入字符为 aa 时，将转换到下一状态 kjk_j ，把 kjk_j 称作 kik_i 的一个后继状态。
  4. S∈KS \in K,是唯一的一个初态。
  5. Z⊆KZ \subseteq K,是一个终集，终态也称可接受状态或结束状态。

初态结点标记 ⇒\Rightarrow、−-，终添结点标记 ++、双圈。

一个DFA 可以表示成一个状态图(或称状态转换图)。假定 DFA MM 含有 mm 个状态,
nn 个输入符号,那么这个状态图含有 mm 个结点,每个结点最多有 nn 个射出,整个图含有唯一一个初态结点和若干个终态结点。

例3.6 DFA M=(S,U,V,Q,a,b,f.S,Q)M=({S,U,V,Q},{a,b},f.S, {Q}),其中 ff 定义为

f(S,a)=Uf(U,a)=Qf(V,a)=Uf(Q,a)=Qf(S,b)=Vf(U,b)=Vf(V,b)=Qf(Q,b)=Qf(S,a) =U f(U,a)=Q f(V,a) =U f(Q,a) = Q \\ f(S,b) =V f(U,b) =V f(V,b) = Q f(Q,b)=Q

作状态图为：

一个 DFA 还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入符号，矩阵元素
表示相应状态和输入符号将转换成的新状态，即行列为 f(k,a)f(k, a)的值，可以用 “⇒\Rightarrow” 标明初态；否则第一行即是初态，相应终态行在表的右端标以 1，非终本标以 0。

例 3.6 矩阵为：

状态\符号 a b （表外）
S U V 0
U Q V 0
V U Q 0
Q Q Q 1

对于 ∑∗\sum^* 中的任何符号串 tt，若存在一条从初态结点到某一终态结点的道路，且这条路上所有弧的标记符连接成的符号串等于 tt，则称 tt 可为 DFA MM 所接受,若 MM 的初态结点同时又是终结点，则空字可为 MM 所识别(接受)。
简单来说就是一个终结符号串能够由初态最终推导至终态，它就是可接受的。

其确定性最终表现在转换函数 ff 的单值性，即对任何状态 kk 和输入符号 aa 通过映射f(k,a)f(k, a) 唯一确定下一个状态；图中每个结点射出弧不超过输入符号数量，且一定是不同输入符号标记的。

不确定有穷自动机 NFA

定义依然是五元组

M=(K,∑,f,S,Z)M = ( K , \sum , f , S , Z )

和 DFA 区别在于

  1. ff 是一个从 K×∑∗K \times \sum^* 到 KK 的全体子集的映像，即 K×∑∗→2kK \times \sum^* \to 2^k，其中 2k2^k 表示 KK 的幂集。

图也是类似，但是结点射出的弧不再有数量和重复的限制，直接使用 ∑∗\sum^* 中的一个串标记。

例3.7 一个NFA M=(0,1,2,3,4,a,b,f,0,2,4)M=({0,1,2,3,4}, {a,b},f,{0},{2,4})，其中:

f(0,a)=0,3f(0.b)=0,1f(1,b)=2f(2.a)=2f(2,b)=2f(3,a)=4f(4,a)=4f(4,b)=4f(0,a)={0,3} \\ f(0.b)={0,1} \\ f(1,b)={2} \\ f(2.a)={2} \\ f(2,b)={2} \\ f(3,a)={4} \\ f(4,a)={4} \\ f(4,b)={4}

图和矩阵就是这样，注意弧的标记：

状态 a b （表外）
0 {0, 3} {0, 1} 0
1 ∅ {2} 1
2 {2} {2} 1
3 {4} ∅ 0
4 {4} {4} 1

NFA 转换为等价的 DFA

一般用子集法作表，以 3.7 的为例

  1. 把初态写在最左边，然后构建已知符号集转移后状态
    状态 a b
    {0} {0,3} {0,1}
  2. 把所有不在状态列的结果移入状态列，对于这些集合继续构建转移后状态
    状态 a b
    {0} {0,3} {0,1}
    {0,3}
    {0,1}
  3. 一直这样将结果移入状态列继续构建，直到所有结果都在状态列中
    DFA 状态 a b
    {0} {0,3} {0,1}
    {0,3} {0,3,4} {0,1}
    {0,1} {0,3} {0,1,2}
    {0,3,4} {0,3,4} {0,1,4}
    {0,1,2} {0,2,3} {0,1,2}
    {0,1,4} {0,3,4} {0,1,2,4}
    {0,2,3} {0,2,3,4} {0,1,2}
    {0,1,2,4} {0,2,3,4} {0,1,2,4}
    {0,2,3,4} {0,2,3,4} {0,1,2,4}

根据这个就得出了 NFA 的 DFA。

DFA 化简

无用（多余）状态：从开始状态任何输入都到达不了的状态，或从这个状态没有通路到达终态。

直接删掉无用状态；然后用分割法：

  1. 把变换至接受（到终态）的状态和非接受的分割为两块
  2. 检查每块转移目标的块存在不同的状态，进行分割
  3. 一直进行 2 直到无法分割
  4. 合并同一块的状态

例：

假设有以下 DFA：

状态 a b 类型
0 1 0 初始
1 2 0 -
2 2 3 -
3 2 0 接受
  1. 初始分割
分割块 状态
P₀（非接受） {0, 1, 2}
P₁（接受） {3}
  1. 检查 P₀ = {0, 1, 2}

检查各状态的转移目标所属的分割块：

状态 δ(a) δ(b) δ(a)所属块 δ(b)所属块
0 1 0 P₀ P₀
1 2 0 P₀ P₀
2 2 3 P₀ P₁

发现状态 2 的 δ(b) 转移到 P₁，而 0, 1 转移到 P₀，需要分割：

分割块 状态
P₀ {0, 1}
P₁ {2}
P₂ {3}
  1. 检查 P₀ = {0, 1}
状态 δ(a) δ(b) δ(a)所属块 δ(b)所属块
0 1 0 P₀ P₀
1 2 0 P₁ P₀

发现状态 0 的 δ(a) 转移到 P₀，而 1 转移到 P₁，需要分割：

分割块 状态
P₀ {0}
P₁ {1}
P₂ {2}
P₃ {3}
  1. 无法再分割，终止

每个状态独立，该 DFA 已是最小化形式。

  1. 唯一性：最小化 DFA 在同构意义下是唯一的
  2. 等价性：最小化 DFA 与原 DFA 接受完全相同的语言
  3. 死状态：如果存在死状态（所有输入都转移到自身），且不是接受状态，可以删除