《编译程序设计原理与技术》笔记之自动机与正规表达式
条评论本笔记基于北京邮电大学出版的李文生编著的《编译程序设计原理与技术》整理
有限自动机是具有离散输入与输出的系统的一种数学模型,系统可以处于有限个内部状态的任何一个之中,系统的当前状态概括了有关过去输入的信息,这些信息对于确定系统在以后的输入上的行为是必需的。
有限自动机有『确定的』和『非确定的』两种,所谓『确定的有限自动机』是指在当前状态下,输入一个符合,有限自动机转换到唯一的下一个状态,称为后继状态;而『非确定的有限自动机』是指在当前状态下输入一个符号,可能有两种以上可选择的后继状态,并且非确定的有限自动机所对应的状态转换图可以有标记为 $\epsilon$ 的边。
正则文法可以用状态转换图非形式的进行表示,这就表明正则文法所对应的语言(正则语言)可以用状态转换图来接受(识别)。有限自动机正是对状态转换图进一步形式化的结果。
1. 状态转换图
状态转换图是一张有限的方向图,其中:
- 结点代表状态用圆圈表示;
- 状态之间用有向边连接;
- 边上的标记表示在射出结点状态下可能出现的输入符号。
一张状态转换图只含有有限个状态(即有限个结点),其中有一个称为初始状态,而可以有若干个(可以为0个)终结状态,终态用双圆圈表示。
2. 确定的有限自动机(DFA)
定义1.1 一个确定的有限自动机 M (记作:DFA M)是一个五元组:
- $\sum$ :是一个字母表,他的每个元素称为一个输入符号
- $Q$ :是一个有限的状态集合,每个元素称为一个状态
- $q_0 \in Q$ :$q_0$ 称为初始状态
- $F \subseteq Q$ : $F$ 称为终结状态集合
- $\delta$ :是转换函数,是一个从 $Q \times \sum$ 到 $Q$ 的单值映射
转换函数 $\delta(q, a) = q^, (其中 q, q^, \in Q , a \in \sum)$ 表示当前状态为 $q$,输入符号为 $a$ 时,自动机将转换到下一个状态 $q^,$ ,$q^,$ 称为 $q$ 的一个后继。
若 $Q = { q1, q_2, \cdots , q_n }, \sum = { a_1, a_2, \cdots, a_n }$ ,则 $Q \times \sum = (\delta(q_i, q_j){n \times m})$ 是一个 n 行 m 列的矩阵,它被称为 DFA M 的状态转换矩阵,也称为转换表。
对 $\sum$ 上的任何符号串 $\omega \in \sum^*$ ,若存在一条从初态结点到终态结点的路径,该路径上每条边的标记连接成的符号串恰好是 $\omega$ ,则称 $\omega$ 为 DFA M 所识别。DFA M 所能识别的符号串的全体记为 $L(M)$ ,称为 DFA M 所识别的语言。
3. 非确定的有限自动机(NFA)
定义1.2 一个非确定的有限自动机 M (记作:NFA M)是一个五元组:
- $\sum$ :是一个字母表,他的每个元素称为一个输入符号
- $Q$ :是一个有限的状态集合,每个元素称为一个状态
- $q_0 \in Q$ :$q_0$ 称为初始状态
- $F \subseteq Q$ : $F$ 称为终结状态集合
- $\delta$ :是一个从 $Q \times \sum$ 到 $Q$ 的子集的映射,即 $\delta \times Q \rightarrow 2^Q$ ,其中 $2^Q$ 是 Q 的幂集,也就是 Q 的所有子集组成的集合。
对 $\sum$ 上的任何符号串 $\omega \in \sum^*$ ,若存在一条从初态结点到终态结点的路径,该路径上每条边的标记连接成的符号串恰好是 $\omega$ ,则称 $\omega$ 为 NFA M 所识别。NFA M 所能识别的符号串的全体记为 $L(M)$ ,称为 NFA M 所识别的语言。
4. 具有 $\epsilon$ - 转移的非确定的有限自动机
如果状态转换图中有标记为 $\epsilon$ 的边,则无法用前面的定义描述因而需要扩充 NFA 的概念。
定义1.3 一个具有 $\epsilon$ - 转移的非确定的有限自动机 M (记作:NFA M)是一个五元组:
- $\sum$ :是一个字母表,他的每个元素称为一个输入符号
- $Q$ :是一个有限的状态集合,每个元素称为一个状态
- $q_0 \in Q$ :$q_0$ 称为初始状态
- $F \subseteq Q$ : $F$ 称为终结状态集合
- $\delta$ :是一个从 $Q \times (\sum \cup { \epsilon } )$ 到 $Q$ 的子集的映射,即 $\delta : Q( \sum\cup { \epsilon } ) \rightarrow 2^Q$ ,其中 $2^Q$ 是 Q 的幂集,也就是 Q 的所有子集组成的集合。
对 $\sum$ 上的任何符号串 $\omega \in \sum^*$ ,若存在一条从初态结点到终态结点的路径,该路径上每条边的标记连接成的符号串恰好是 $\omega$ ,则称 $\omega$ 为 NFA M 所识别。NFA M 所能识别的符号串的全体记为 $L(M)$ ,称为 NFA M 所识别的语言。
5. 非确定的有限自动机的确定化
定理 1.1 对任意一个 NFA M,都存在一个与之等价的 DFA D,即 L(M) = L(D)。
定理 1.2 对任何一个具有 $\epsilon$ - 转移的 NFA M,都存在一个等价的不具有 $\epsilon - $ 转移的 NFA N。
推论 1 对任何一个具有 $\epsilon$ - 转移的 NFA M,都存在一个与之等价的 DFA D。
下面研究『非确定的有限自动机的确定化』,由 NFA 构造等价的 DFA 。
因为 DFA D 的每一个状态对应于 NFA M 的一个状态子集,所以构造状态转换表 DTT 时,对给定的输入符号串,使 D 『并行地』模拟 M 所能产生的所有可能的转换,令 q 为 NFA M 的状态,T 为 NFA M 的状态子集,引入以下操作:
- ε-闭包:
- ϵ_closure(q) 表示从 q 出发,经过 $\epsilon$ - 道路可以到达状态 $q^,$ 。
- ϵ_closure(T) = $\stackrel{n}{\underset{i = i}\cup}$ ϵ_closure$(q_i)$ 其中 $q_i \in T$ ,表示 T 中任一状态出发,经过 $\epsilon$ - 道路后可以到达的状态集合。
- 求 T 的 a 弧转换:
- $move(T, a)$ 表示从某个状态 $q_i \in T$ 出发,经过输入符号 a 之后可到达的状态的集合。
例如下图这个 NFA N:
它是一个具有 $\epsilon$ - 转移的非确定的有限自动机 N ,是一个五元组:$ N= ( \sum , Q , q_0 , F, \delta )$ ,即为(弧集合,状态集合,初始状态,终结状态集合,转换函数)
,所以由图可知:NFA N = ({a,b}, {0,1,2,3,4,5,6,7,8,9,10}, {0}, {10}, δ)
。
假定 DFA D 的初态为 A,则 A = ϵ_closure(0) = { 0, 1, 2, 4, 7}。
从初态 A 出发,构造 DFA D 的其余状态如下:
DTT[A, a] = ϵ_closure(move(A, a)) = ϵ_closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8} = B
DTT[A, b] = ϵ_closure(move(A, b)) = ϵ_closure(5) = {1, 2, 4, 5, 6, 7} = C
DTT[B, a] = ϵ_closure(move(B, a)) = ϵ_closure({3, 8}) = B
DTT[B, b] = ϵ_closure(move(B, b)) = ϵ_closure({5, 9}) = {1, 2, 4, 5, 6, 7, 9} = D
DTT[C, a] = ϵ_closure(move(C, a)) = ϵ_closure({3, 8}) = B
DTT[C, b] = ϵ_closure(move(C, b)) = ϵ_closure(5) = C
DTT[D, a] = ϵ_closure(move(D, a)) = ϵ_closure({3, 8}) = B
DTT[D, b] = ϵ_closure(move(D, b)) = ϵ_closure({5, 10} = {1, 2, 4, 5, 6, 7, 10} = E
DTT[E, a] = ϵ_closure(move(D, a)) = ϵ_closure({3, 8}) = B
DTT[E, b] = ϵ_closure(move(E, b)) = ϵ_closure(5) = C
至此,不再有新的状态出现,构造过程结束。
共构造了 5 个状态,即 A、B、C、D、E,其中 A 为初态,E 为终态,因为 E 的状态集合中包括原 NFA N 的终态 10。
可以借助表格来观察整个求解过程,每次求解后如果产生新集合,就会记录下来继续算,直到没有新集合为止。
ε_closure(move(T,a)) | ε_closure(move(T,b)) | |
---|---|---|
A | B | C |
B | B | D |
C | B | C |
D | B | E |
E | B | C |
最终状态转换图如下:
此 DFA D 识别的语言同样为 $L(D) = { (a|b)^*abb}$ ,由此可知构造出来的 DFA D 与 NFA N 是等价的。
6. DFA 的化简
无关状态:
- 多余状态:从初态出发到达不了的状态。
- 死状态:从该状态无法到达终态
去掉这些无关状态之后得到的等价的状态转换图,它们的 $L(S_i) = L(S_j)$,称它们为等价状态,否则称它们为可区分状态。
DFA的化简步骤举一个『栗子』来学习一下:
我们把前面确定化的 DFA N 在进行一次化简:
第一步:把 DFA N 的状态集合划分为子集,使每个子集中的状态相互等价,不同子集中的状态相互等价,不同子集中的状态可区分。
首先,把 DFA N 的状态集合划分为两个子集:终态子集 {4} 和非终态子集 {0, 1, 2, 3}。由于终态子集只含有一个状态 4,固不可再分。
然后考察非终态子集 {0, 1, 2, 3}。
- 对于输入符号 a,状态 0 ~ 3 都转换到状态 1,所以对于输入符号 a 而言,该子集不能再划分。
- 对于输入符号 b,状态 0,1,2都转换到子集 {0, 1, 2, 3} 中的一个状态,而状态 3 则转换到状态子集 {4} 中的状态。所以应该把子集 {0, 1, 2, 3} 划分为两个新的子集 {0, 1, 2} 和 {3}。
这时,DFA N 的状态集合被划分为三个子集,即 {0, 1, 2} 、{3}、{4}。
其次,考察子集 {0, 1, 2}。
- 对于输入符号 a,状态 0 ~ 2 都转换到状态 1,所以对于输入符号 a 而言,该子集不能再划分。
- 对于输入符号 b,状态 0,2 都转换状态 2,而状态 1 则转换到状态 3。由于 1 和 3 分属于不同的状态子集,所以应该把子集 {0, 1, 2} 划分为两个新的子集 {0, 2} 和 {1}。
这时,DFA N 的状态集合被划分为四个子集,即 {0, 2} 、{1}、{3}、{4}。
最后,考察子集 {0, 2}。
- 对于输入符号 a,状态 0 和 2 都转换到状态 1,所以对于输入符号 a 而言,该子集不能再划分。
- 对于输入符号 b,状态 0 和 2 都转换到状态 2,所以对于输入符号 b 而言,该子集不能再划分。
于是,DFA N 的状态集合最终被划分为四个子集,即 {0, 2} 、{1}、{3}、{4}。
第二步:为每个子集选择一个代表状态。选择 0 为子集 {0, 2} 的代表状态,由于其余子集都只有一个状态,故状态 1,2,3 为它们的代表状态。
至此,画出 DFA N’ 状态转换表和状态转换图。
状态 | a | b |
---|---|---|
0(初态) | 1 | 0 |
1 | 1 | 2 |
2 | 1 | 3 |
3(终态) | 1 | 0 |
7. 正规表达式
用正规表达式可以精确的定义集合,定义 Pascal 语言标识符的正规表达式:$letter(letter|digit)^*$
对于字符表 $\sum$ 上对正规表达式有如下定义:
- $\epsilon$ 是正规表达式,它表示的语言是 ${\epsilon}$
- 如果 $a\in\sum$ ,则 a 是正规表达式,它表示的语言是 {a}
- 如果 r 和 s 都是正规表达式,它标识的语言是 L(r) 和 L(s),则:
- $(r)|(s)$ 是正规表达式,表示的语言是 $L(r)\cup L(s)$
- $(r)(s)$ 是正规表达式,表示的语言是 $L(r)L(s)$
- $(r)^+$ 是正规表达式,表示的语言是 $(L(r))^+$
- $(r)$ 是正规表达式,表示的语言是 $L(r)$
正规表达式表示的语言叫做正规集。
正规表达式的书写约定:
- 一元闭包 * 具有最高优先级,并且遵从左结合
- 连接运算的优先级次之,遵从左结合
- 并运算 | 的优先级最低,遵从左结合
正规表达式遵从的代数定律:
8. 正规表达式与有限自动机的等价性
对任何一个正规表达式 r,都存在一个 FA M,使 L(r) = L(M),反之亦然。
8.1. 正则表达式转 NFA
转换规则如图,对正规表达式 r 进行分裂、加入新的结点,知道每条边的标记都为基本符号为止。
举个『栗子』:有正规表达式 $(a|b)^*abb$ ,为之构造等价的 NFA。
首先为该正则表达式构造拓广转换图,然后根据该正则表达式的构成依据上图的转换规则,对表达式进行分裂,知道每条边的标记都是 $\sum$ 上的符号或 $\epsilon$ 为止,即得到与该正规表达式等价的 NFA。
8.2. NFA 转正则表达式
转换规则如图,逐步消去 N 中的中间结点,直到只剩下结点 i 和 f 为止。在消去结点的过程中,逐步用较复杂的正规表达式来标记有向边。
举个『栗子』:有如下的 NFA M,试构造与之等价的正规表达式 r。
由于该 NFA M 仅有一个初态和一个终态,故不用增加新的结点,可直接从 NFA M 出发,反复利用替换规则,逐步消去中间结点,直到只剩下初态 0 和终态 7 为止,则从 0 到 7 的有向边的标记即所求正则表达式,过程如图:
- 本文链接:《编译程序设计原理与技术》笔记之自动机与正规表达式
- 发布时间:2019年03月04日 - 11:06:06
- 更新时间:2021年02月03日 - 6:56:56
- 版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 CN 许可协议。转载请注明出处!
分享