本笔记基于北京邮电大学出版的李文生编著的《编译程序设计原理与技术》整理

有限自动机是具有离散输入与输出的系统的一种数学模型,系统可以处于有限个内部状态的任何一个之中,系统的当前状态概括了有关过去输入的信息,这些信息对于确定系统在以后的输入上的行为是必需的。

有限自动机有『确定的』和『非确定的』两种,所谓『确定的有限自动机』是指在当前状态下,输入一个符合,有限自动机转换到唯一的下一个状态,称为后继状态;而『非确定的有限自动机』是指在当前状态下输入一个符号,可能有两种以上可选择的后继状态,并且非确定的有限自动机所对应的状态转换图可以有标记为 $\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 的有向边的标记即所求正则表达式,过程如图: