形式语言与自动机理论-03-有限状态自动机

本节介绍一种自动机:有限状态自动机。后文将说明其与正则语言的关系。

DFA 确定性有限状态自动机

一个确定性有限状态自动机(Deterministic Finite State Automaton, DFSA/DFA)由以下元组定义:

\[M = (Q, \Sigma, \delta, q_0, Q_{acc})\]

其中各部分的意义为:

  • \(Q\) 为一有限非空的集合,称为状态集

  • \(\Sigma\) 为有限非空的集合,称为字符集或字母表。其与形式语言中字母表的意义相同。

  • \(\delta\) 为映射 \(\delta : Q \times \Sigma \to Q\),称为状态转移函数。其表明了若当前状态为 \(q_{curr}\),当前所读到的字符为 \(\sigma_{curr}\),那么自动机的状态改变为 \(q_{next} = \delta(q_{curr}, \sigma_{curr})\)

    有时也会以状态转移表来表示 \(\delta\)。此时定义 \(\delta \subseteq Q \times \Sigma \times Q\),其中有 \((q_{curr}, \sigma_{curr}, q_{next}) \in \delta \iff \delta(q_{curr}, \sigma{curr}) = q_{next}\).

    由于此处要求 \(\delta\) 为映射,因此以状态转移表定义时要求 \(\delta\) 中所有元素的前两个部分两两不同。

  • \(q_0 \in Q\) 为一特殊的状态,称为初始状态。初始状态有且仅有一个。

  • \(Q_{acc} \subseteq Q\) 为接受状态集。该定义对于是否 \(Q_{acc} \ne Q\) 以及 \(q_0 \not\in Q_{acc}\) 并不作任何断言。

以上抽象的定义可以通过图的方法展示出来,该方法当状态数量不多时特别有用。具体的方法是,图的节点表示 \(Q\),用没有来源的输入箭头标明初始状态 \(q_0\),用两个同心圆表示接受状态 \(Q_{acc}\)。若有 \((q_{curr}, \sigma_{curr}, q_{next}) \in \delta\) 则图中有从节点 \(q_{curr}\) 到节点 \(q_{next}\) 的有向边,并以 \(\sigma_{curr}\) 标记该有向边。

考虑定义如下的 FSA:

\[ \begin{aligned} M &= (Q, \Sigma, \delta, q_0, Q_{acc})\\ Q &= \{A, B, C, D\}\\ \Sigma &= \{0, 1\}\\ q_0 = A &\in Q\\ \delta &= \left\{ \begin{array}{l} (A, 0, B)\\ (A, 1, A)\\ (B, 0, B)\\ (B, 1, C)\\ (C, 0, D)\\ (C, 1, A)\\ (D, 0, D)\\ (D, 1, D) \end{array} \right\}\\ Q_{acc} &= \{D\}\\ &\subset Q \end{aligned} \]

其中状态转移也可表达为

\[ \begin{array}{l|ll} \text{当前状态\符号} & 0 & 1 \\ \hline A & B & A \\ B & B & C \\ C & D & A \\ D & D & D \end{array} \]

我们注意到,由于该自动机的状态转移表中每一格仅有一个元素,因此该自动机是确定性的。

其对应的状态图为:

我们说一个确定性状态图(或者其描述的确定性有限状态自动机)接受一个字符串 \(\sigma_1\sigma_2\dots \sigma_n\),如果有一条从起始状态到某个接收状态以 \(\sigma_1\sigma_2\dots\sigma_n\) 标记的路径。称该状态机接受的所有字符串的集合为其识别的语言。

上述可形式化地定义如下:

首先我们将状态转移函数 \(\delta\) 拓展至 \(Q \times \Sigma^* \to Q\):

\[ \delta^*(q, s) = \begin{cases} q, &s = \varepsilon\\ \delta(q, \sigma), &s = \sigma \in \Sigma\\ \delta(\delta^*(s', q), \sigma), &s = s'\sigma \wedge \delta^*(s',q)! \wedge \delta(\delta^*(s', q), \sigma)!\\ \text{未定义}, &\text{除以上情况外} \end{cases} \]

其中,我们允许 \(\delta, \delta^*\) 为不完全函数,或者称为偏函数。取拓展前的版本为例,即 \(\delta\) 在某些 \((\sigma, q) \in Q \times \Sigma\) 上没有定义。我们用记号 \(\delta(q, \sigma)!\) 表示 \(\delta\) 在参数 \((q, \sigma)\) 上有定义。

允许不完全的定义完全是为了定义的简洁考虑的。我们可以人为地给每个自动机加上一个特殊的状态,记作 \(q_{rej}\),并设所有未定义的 \(\delta(q, \sigma) := q_{rej}\) (这同样包括 \(\forall \sigma\in\Sigma, \delta(q_{rej}, \sigma) = q_{rej}\)),于是便不存在 \(s\) 使得 \(\delta^*(q_{rej}, s) \in Q_{acc}\),因此可以在不改变所识别的语言的前提下使得 \(\delta\) 仍为全函数。当然对于有的状态机来说,我们就要显式地多定义许多项转移了。

若我们视符号为长度为 1 的字符串,则可以不做区分地用 \(\delta\) 指代拓展前后的状态转移函数。

于是便可定义

\[ L(M) = \{s\in\Sigma^*: \delta(q_0, s) \in Q_{acc}\} \subseteq \Sigma^* \]

\(L(M)\) 为状态机 \(M\) 识别的语言。若 \(s \in L(M)\),称 \(s\)\(M\) 接受,否则称 \(s\)\(M\) 拒绝。

据此定义,我们可以看到前例中有字符串 \(01101001\) 被状态机 \(M\) 接受。

最小化 DFA

对于任意 DFA \(M = (Q, \Sigma, \delta, q_0, Q_{acc})\),称状态 \(q_1, q_2 \in Q\) 是不可区分的,若有

\[ \forall s \in \Sigma^*. \delta(q_1, s) \in Q_{acc} \iff \delta(q_2, s) \in Q_{acc} \]

注意不可区分关系是自反的,对称的,传递的,因此不可区分关系在集合 \(Q\) 上定义了一个等价关系。

显然,对于 \(q_1 \in Q/Q_{acc}\), \(q_2 \in Q_{acc}\) (或相反),总是有 \(q_1\)\(q_2\) 是可区分的,此时取 \(s = \varepsilon\).

于是有标记不可区分簇算法如下:

  • stage 0: 标记所有对 \((q_1, q_2)\),其中 \(q_1 \in Q/Q_{acc}\), \(q_2 \in Q_{acc}\)(或相反)为可区分的

  • 重复进行,直到没有新的对被标记

    stage \(i\) (\(i \ge 1\)): 考虑任何尚未标记为可区分的对 \((q_1, q_2)\),若存在 \(\sigma \in \Sigma\),使得对 \((\delta(q_1, \sigma), \delta(q_2, \sigma))\) 已被标记,则标记 \((q_1, q_2)\)

此时合并所有不可区分簇。

P. Linz 给出的证明表示,对于任何正则语言,存在唯一的识别该语言的最小 DFA。即,若 DFA \(M_1, M_2\) 识别该语言,最小化 \(M_1, M_2\) 将得到同一个 DFA,同时,若 DFA \(M_1, M_2\) 皆为最小,则有 \(M_1 = M_2\).

NFA 非确定性有限状态自动机

我们可以在 DFA 的基础上如此放宽定义:首先拓展状态转移函数至 \(\delta': Q \times \Sigma \to \mathcal{P}(Q)\),即给定当前状态 \(q_{curr}\),当前读入字符 \(\sigma_{curr}\),有 \(\delta'(q_{curr}, \sigma_{curr}) \subseteq Q\),即允许转移至多个状态。注意,这说明了我们可以同时处于多个状态中,而并非状态机通过某种方法,例如随机选择,转移到多个状态中的某一个中。

如此一来由于我们可以同时处于多个状态中,于是也有必要拓展状态转移函数的值域如:\(\delta''(Q_{curr}, \sigma_{curr}) = \displaystyle \bigcup_{q_{curr} \in Q_{curr}} \delta'(q_{curr}, \sigma_{curr})\), \(\delta'': \mathcal{P}(Q) \times \Sigma \to \mathcal{P}(Q)\)。我们称这样的有限状态自动机为非确定性有限状态自动机(nondeterministic finite state automata, NFSA/NFA).

若我们视 \(\delta(q, \sigma) = \delta''(\{q\}, \sigma)\),则可发现 DFA 是 NFA 的特例,于是后文将不做区别地使用 \(\delta\) 代指 \(\delta''\),而由上下文确定 \(\delta\) 的值域/定义域。

当以状态转移表来表示 NFS 的状态转移函数 \(\delta\) 时,可定义 \(\delta \subseteq Q \times \Sigma \times Q\),其中有 \((q_{curr}, \sigma_{curr}, q_{next}) \in \delta \iff \delta(\{q_{curr}\}, \sigma_{curr}) \supseteq \{q_{next}\}\).

类似地,我们像定义 DFA 时那样继续将状态转移函数拓展至字符串上。于是有

\[ L(M) = \{s\in\Sigma^*: \exists q \in Q_{acc}, \delta(\{q_0\}, s) = q \wedge q \in Q_{acc}\} \]

等价地,也可说

\[ L(M) = \{s\in\Sigma^*: \delta(\{q_0\}, s) \cap Q_{acc} \ne \emptyset\} \]

下面是一个非确定性状态机的例子。

子集构造算法(subset construction algorithm)

虽然前文称 NFA 是由 DFA 的定义拓展来的,然而事实上给定一个 NFA,有算法可以构造出接受相同语言的 DFA (虽然不一定是最小的)。又由于根据定义有 \(DFA \subseteq NFA\),该算法构造性地证明了 \(DFA \equiv NFA\),即两种计算模型的计算能力是等价的或者说一个语言若能被 NFA/DFA 识别,则一定有能识别它的 DFA/NFA.

该算法来源于如下观察:对于 NFA \(M_{NFA} = (Q_{NFA}, \Sigma, \delta_{NFA}, q_{0, NFA}, Q_{acc, NFA})\) 来说,由于集合 \(Q_{NFA}\) 有限,有 \(\big| \mathcal{P}(Q_{NFA}) \big| = 2^{\big| Q_{NFA} \big|}\) 有限.

于是可记 \(Q_{DFA} \ni q_{curr, DFA} = Q_{curr, NFA} \subseteq Q_{NFA}\),从而有 \(Q_{DFA}\) 为有限集合,符合 DFA 定义的要求。那么便可以得到等价的状态转移函数 \(\delta_{DFA}(q, \sigma) := \delta_{NFA}(q, \sigma)\)。注意由于有 \(Q_{DFA} \subseteq \mathcal{P}(Q_{NFA})\) 为集合的集合,有 \(\delta_{DFA}: Q_{DFA} \times \Sigma \to Q_{DFA} = \mathcal{P}(Q_{NFA}) \times \Sigma \to \mathcal{P}(Q_{NFA})\),注意其定义域与值域和 \(\delta_{NFA}\) 一模一样。这就是该算法的名称“子集构造”的由来。

当然,由于 \(Q_{DFA} \subseteq \mathcal{P}(Q_{NFA})\),有 \(\big| Q_{DFA} \big| \le \big| \mathcal{P}(Q_{NFA}) \big| = 2^{\big| Q_{NFA} \big|}\),于是我们至多需要构造指数级别个状态,而这其中可能大部分工作都是浪费,因为这些状态并不见得在 \(M_{NFA}\) 中可达。于是在 \(M_{NFA}\) 上使用图遍历算法,除了个别极端情况外,都可以将状态的数量降到合理的范围内。

下面给出一个例子,其中可使用队列或者栈数据结构记录当前待处理的子集。

将如下 NFA 化简为 DFA:

使用子集构造算法,可得 DFA 的状态转移表:

\[ \begin{array}{lll} \text{当前状态\符号} & 0 & 1 & 新状态\\ \hline &&& \{A\}\\ \{A\} & \{A, B\} & \{A\} & \{A, B\}\\ \{A, B\} & \{A, B\} & \{A, C\} & \{A, C\}\\ \{A, C\} & \{A, B, C\} & \{A, C\} & \{A, B, C\}\\ \{A, B, C\} & \{A, B, C\} & \{A, C\} \end{array} \]

于是等价的 DFA 如下:

注意,子集构造算法得到的并不一定是最小的等价 DFA。该例中有状态 \(\{A, B, C\}\)\(\{A, C\}\) 可合并为一个状态。我们将在后文讨论最小化 DFA 的算法。

\(\varepsilon\)-NFA

更进一步的拓展来源于对如下事实的观察:对于任何字符串 \(s \in \Sigma^*\) 来说,皆有 \(s = \varepsilon s\),即 \(\varepsilon\) 是任何字符串的前缀。因此我们可拓展状态转移函数为:

\[ \delta^\varepsilon: \mathcal{P}(Q) \times \Sigma \to \mathcal{P}(Q) \\ \delta^\varepsilon(Q_{acc}, \sigma) = \bigcup_{q \in Q_{acc}} \delta^\varepsilon(\delta(q, \varepsilon), \sigma) \cup \delta(q, \sigma) \cup \delta^\varepsilon(\delta(q, \sigma), \varepsilon) \]

我们称所有形如 \(\delta(q, \varepsilon)\) 的转移为 \(\varepsilon\)-转移。我们可以将 \(\varepsilon\)-转移 理解为是状态机自发的行为,即不需要读入字符即可产生的转移行为。由于 \(\varepsilon\)-转移 使得我们必然会同时处于多个状态(取决我们视 \(s = s\) 还是 \(s = \varepsilon \cdot s\)),于是该定义使得状态机必然是非确定性的,而称定义中有 \(\varepsilon\)-转移 的状态机为 \(\varepsilon\)-NFA。

在该定义下,为了方便表达,我们也可以进一步取消仅有一个初始状态的要求,并定义 \(Q_0 \subseteq Q\) 为初始状态集合。因为这样的定义等价于有 \(q'_0 \in Q' = Q \cup \{q'_0\}\) 且对于所有 \(q_0 \in Q_0\) 皆有 \(\delta(q'_0, \varepsilon) = q_0\)。于是我们发现对于 \(\varepsilon\)-NFA 来说是否限制仅有一个初始状态分别得到的定义是等价的。

\(\varepsilon\)-转移 移除算法

该算法构造性地证明了 \(\varepsilon\)-NFA 与 NFA 的等价性。

以状态转移图来描述,考虑 \(\varepsilon\)-NFA \(M\),以下算法构造等价的 NFA \(M'\):

  1. 复制 \(M\)\(M'\),移除 \(M'\) 中所有的 \(\varepsilon\)-转移,以及所有进入转移皆为 \(\varepsilon\)-转移的节点,初始节点除外。

  2. 对于 \(M\) 中每一条由数个 \(\varepsilon\)-转移 接一个以 \(b \in \Sigma\) 标记的转移构成的路径:

    \[ p \stackrel{\varepsilon}{\to} \bigcirc \stackrel{\varepsilon}{\to} \cdots \stackrel{\varepsilon}{\to} \bigcirc \stackrel{b}{\to} q\]

    \(M'\) 中加入转移 \(p \stackrel{b}{\to} q\),其中允许有 \(p = q\)

  3. \(M\) 中对于每一条完全由 \(\varepsilon\)-转移 组成的路径

    \[ p \stackrel{\varepsilon}{\to} \bigcirc \stackrel{\varepsilon}{\to} \cdots \stackrel{\varepsilon}{\to} \circledcirc \]

    \(M'\) 中标记 \(p\) 为接受状态。

考虑将如下 \(\varepsilon\)-NFA:

其等价的 NFA 如下:


于是我们有 \(DFA \equiv NFA \equiv \varepsilon\text{-}NFA\).

Addendum

给定描述一有限状态自动机的状态转移图,称其中一节点为

可达的(reachable),若存在至少一条从 \(q_0\) 至该节点的路径;

补可达的(co-reachable),若存在至少一条从该节点至任意接受节点的路径。

若给定有限状态自动机中所有状态皆既是可达的又是补可达的,则称该状态机是整洁的(trim)。

称移除给定有限状态自动机中所有非可达和非补可达状态的操作为修整。

由于我们主要关心有限状态自动机所识别的语言,且移除非可达的和非补可达的状态并不会改变其识别的语言,因此我们总是假设给定有限状态自动机是整洁的(若不然可通过修整的操作得到识别语言意义上等价的有限状态自动机)。