跳转至

Finite Automata⚓︎

5074 个字 3 行代码 预计阅读时间 25 分钟

Deterministic Finite Automata⚓︎

有限自动机(finite automata) 接收字符串输入并以输入纸带(input tape) 的形式传递,之后仅输出一个关于是否认为输入可接受(acceptable) 的指示。让有限自动机成为现实计算机的一种限制模型的是处理器外内存的缺失(处理器内仅有固定有限的容量

更多有关有限自动机(更准确的说,是确定性有限自动机(deterministic finite automata))操作的细节:

  • 输入磁带被划分为一个个方格,每个方格表示字符串上的单个符号
  • 整个机器的主要部分可看作是在任意时刻处于其中一种不同的内部状态(state)(总的状态数是有限的)的一个“黑盒”
  • 这个“黑盒”叫做有限控制(finite control),它借助一个可移动的读头(reading head) 感知输入带上任意位置所写的符号
  • 一开始,读头置于磁带的最左端方格,有限控制设定为初始状态(initial state)
  • 每隔固定的一段时间,自动机从输入带上读取一个符号,随后根据当前状态及所读符号进入新状态,读完后读头会向右移动一格
  • 上述过程反复进行,直到到达输入字符串的末端时,自动机通过其结束时所处的状态来表示对所读内容的接受与否
    • 如果它停在一个最终状态(final state) 集合中的某个状态上,则该输入字符串被视为被接受的(accepted)
    • 机器所接受的语言就是它所接受的字符串集合

下面给出确定性有限自动机的形式化定义:

定义

确定性有限自动机是一个五元组 \(M = (K, \Sigma, \delta, s, F)\),其中

  • \(K\)状态的有限集合
  • \(\Sigma\):字母表
  • \(s \in K\)初始状态
  • \(F \subseteq K\)最终状态集合
  • \(\delta\)转移函数(transition function),一个从 \(K \times \Sigma\) \(K\) 的函数

如果 \(M\) 处在状态 \(q \in K\),且从输入纸带上读到符号 \(a \in \Sigma\),那么 \(\delta(q, a) \in K\) 是一个唯一确定的(下一个)状态。

粗略来说,自动机对输入字符串进行计算,可用一个表示机器在连续时刻状态的配置(configuration) 序列表示。但由于确定性有限自动机不允许将其读头移回已读取的输入字符串部分,因此读头左侧的字符串部分不会影响机器的未来操作。因此,一个配置由当前状态未读字符串部分决定。换言之,确定性有限自动机 \((K, \Sigma, \delta, s, F)\) 的一个配置是 \(K \times \Sigma^*\) 中的任意元素(对于上图,就是 \((q_2, ababab)\)

当且仅当机器可以通过一次移动从一个配置转移到另一个时,称二元关系 \(\mapsto_M\) \(M\) 的两个配置之间成立。

  • 因此,如果 \((q, q)\) \((q', w')\) \(M\) 的两个配置,那么 \((q, w) \mapsto_M (q', w')\) 当且仅当对于某个符号 \(a \in \Sigma\),有 \(w = aw'\) 并且 \(\delta(q, a) = q'\) 时成立,此时我们说 \((q, w)\) 在一步内产生(yields in one step) \((q', w')\)
  • 注意实际上 \(\mapsto_M\) 是从 \(K \times \Sigma^+\) \(K \times \Sigma^*\) 的一个函数,也就是说,除了形如 \((q, e)\) 的配置外,每个配置都有唯一确定的下一个配置
  • 而形如 \((q, e)\) 的配置意味着 \(M\) 已经读完所有输入,因此停止处理
  • 用符号 \(\mapsto_M^*\) 表示 \(\mapsto_M\) 自反传递闭包\((q, w) \mapsto_M^* (q', w')\) 就表示 \((q, w)\) 0 步或多步内产生了(yields in one step) \((q', w')\)
    • 当且仅当存在状态 \(q \in F\),使得 \((s, w) \mapsto_M^* (q, e)\) 成立时,字符串 \(w \in \Sigma^*\) \(M\) 接受
    • \(M\) 接受的语言 \(L(M)\) 是所有被 \(M\) 接受的字符串的集合
例子

假如确定性有限状态机 \(M = (K, \Sigma, \delta, s, F)\),其中:

\[ \begin{align*} K &= \{q_0, q_1\}, \\ \Sigma &= \{a, b\}, \\ s &= q_0, \\ F &= \{q_0\}, \end{align*} \]

\(\delta\) 为:

\(q\) \(\sigma\) \(\delta(q, \sigma)\)
\(q_0\) \(a\) \(q_0\)
\(q_0\) \(b\) \(q_1\)
\(q_1\) \(a\) \(q_1\)
\(q_1\) \(b\) \(q_0\)

不难发现 \(L(M)\) 表示的是有偶数个 \(b\) 的字符串。

除了表格形式外,我们也可以用状态图(state diagram) 表示转移函数,如下所示:

下面设计一个确定性有限状态机 \(M\),它接受语言 \(L(M) = \{w \in \{a, b\}^*: w \text{ does not contain three consecutive b's}\}\),其中:

\[ \begin{aligned} K &= \{q_0, q_1, q_2, q_3\}, \\ \Sigma &= \{a, b\}, \\ s &= q_0, \\ F &= \{q_0, q_1, q_2\}, \end{aligned} \]

\(\delta\) 为:

\(q\) \(\sigma\) \(\delta(q, \sigma)\)
\(q_0\) \(a\) \(q_0\)
\(q_0\) \(b\) \(q_1\)
\(q_1\) \(a\) \(q_0\)
\(q_1\) \(b\) \(q_2\)
\(q_2\) \(a\) \(q_0\)
\(q_2\) \(b\) \(q_3\)
\(q_3\) \(a\) \(q_3\)
\(q_3\) \(b\) \(q_3\)

对应的状态图如下:

可以看到,如果出现连续 3 个 \(b\) 的情况,状态机就会陷入(trap) \(q_3\) 这唯一的非最终状态,因而该字符串无法为自动机接受。我们称 \(q_3\) 死亡状态(dead state)。

Nondeterministic Finite Automata⚓︎

自动机的非确定性(nondeterminism) 是指状态的改变仅部分取决于当前状态和输入符号。也就是说对于给定的当前状态和输入符号,允许有多种可能的下一状态;自动机可能会选择这些合法的下一状态中的任意一个,而这个选择不受模型的影响。

这种不确定性是对有限状态机的符号化推广 (notational generalization),能够极大简化对自动机的描述。并且稍后我们会看到:每个非确定性有限自动机等价于某个确定性有限自动机

之后就分别用 DFANFA 分别指代确定性有限自动机和非确定性有限自动机。

例子

假如设计一个自动机 \(M\),它能够接受语言 \(L = (ab \cup aba)^*\)。对应的 DFA NFA 的状态图分别如下:

- 可以看到,当输入为 \(b\),状态为 \(q_1\) 时,下一状态既可以是 \(q_0\),也可以是 \(q_2\) - 如果存在某种方式,从初始状态(\(q_0\))出发,沿着标记有字符串符号的箭头到达一个最终状态,那么该字符串是可接受的 - 注意到从状态 \(q_0\) 出发,当输入为 \(b\) 时没有可进入的状态 - 这是非确定性有限自动机的另一个特点:在某些状态和输入符号的组合下也可能没有任何可行的转移路径

允许 NFA 上有带空字符串 \(e\) 的箭头,这能让自动机在不读取任何输入的情况下实现状态转移。

NFA 的形式化定义如下:

定义

非确定性有限自动机(nondeterministic finite automata, NFA) 是一个五元组 \(M = (K, \Sigma, \Delta, s, F)\),其中:

  • \(K\)状态的有限集合
  • \(\Sigma\):字母表
  • \(s \in K\)初始状态
  • \(F \subseteq K\)最终状态集合
  • \(\Delta\)转移关系(transition relation),一个从 \(K \times \(Sigma \cup \{e\}) \times K\) 的子集

元组 \((q, a, p) \in \Delta\) 被称为 \(M\) 转移(transition)。当 \(M\) 处在状态 \(q\) 且下一个输入符号为 \(a\) 时,\(M\) 会可能会进行 \((q, a, p)\) \((q, e, p)\) 中的任何一种转移。

NFA 也有和 DFA 相似的概念:

  • \(M\) 配置 \(K \times \Sigma^*\) 中的一个元素
  • 配置间的关系 \(\mapsto_M\)一步内产生)的定义如下:当前仅当存在 \(u \in \Sigma\) 使得 \(w = uw'\),且 \((q, u, q') \in \Delta\) 时,\((q, w) \mapsto_M (q', w')\)
    • \(\mapsto_M\) 不必是函数,因此可能存在一对多的映射
    • \(\mapsto_M^*\) \(\mapsto_M\) 的自反传递闭包;当且仅当 \(\exists q \in F\)\((s, w) \mapsto_M^* (q, e)\),称字符串 \(w \in \Sigma^*\) \(M\) 接受
例子

下面设计了一个接受出现模式为 \(bb\) \(bab\) 的字符串的 NFA,其中:

\[ \begin{aligned} K &= \{q_0, q_1, q_2, q_3, q_4\}, \\ \Sigma &= \{a, b\}, \\ s &= q_0, \\ F &= \{q_4\} \\ \Delta & = \{(q_0, a, q_0), (q_0, b, q_0), (q_0, b, q_1), \\ & (q_1, b, q_2), (q_1, a, q_3), (q_2, e, q_4), \\ & (q_3, b, q_4), (q_4, a, q_4), (q_4, b, q_4)\} \end{aligned} \]

对应的状态图如下:

对于输入 \(bababab\),即有可能陷入 \(q_0\) 状态出不去:

\[ \begin{aligned}(q_0,bababab)&\mathsf{\vdash}_M\left(q_0,ababab\right)\\&\vdash_M(q_0,babab)\\&\vdash_M(q_0,abab)\\&\vdots\\&\vdash_M(q_0,e)\end{aligned} \]

也有可能顺利抵达最终状态:

\[ \begin{aligned}(q_0,bababab)&\vdash_M(q_1,ababab)\\&\vdash_M(q_3,babab)\\&\vdash_M(q_4,abab)\\&\vdash_M(q_4,bab)\\&\vdash_M(q_4,ab)\\&\vdash_M\left(q_4,b\right)\\&\vdash_M(q_4,e)\end{aligned} \]

NFA 而言,只要存在一种可能到达最终状态的序列,说明对应的字符串是可被接受的,因此 \(bababab \in L(M)\)

\(\Sigma = \{a_1, \dots, a_n\}\ (n \ge 2)\)。考虑以下语言: $$ L={w:\text{there is a symbol }a_i\in\Sigma\text{ not appearing in }w} $$

也就是说只要字符串包含了字母表内的所有符号就无法被自动机接受,而其他情况均会被接受。这样的 NFA 相对比较容易设计:

  • \(K\) 包含 \(n+1\) 个状态 \(\{s, q_1, \dots, q_n\}\)
  • 且这些状态均为最终状态,即 \(F = K\)
  • \(\Delta\) 仅包含两类转移
    • 初始转移(initial transition):\((s, e, q_i)\ (1 \le i \le n)\)
    • 主转移(main transition):\((q_i, a_j, q_i)\ (i \ne j)\)

对应的状态图如下(\(n=3\)

可以看到,\(M\) 通过猜测输入中缺失的符号来开始运算。NFA 的强大之处在于它会把每一种可能都走一遍,因此永远会走出一条正确的路,从而成功得到最终结果。

值得注意的是,DFA 只是 NFA 的一种特殊类型:在 DFA 中,转移关系是一个从 \(K \times \Sigma\) 映射到 \(K\) 的函数。当且仅当 \(\Delta\) 没有形如 \((q, e, p)\) 的转移,且 \(\forall q \in K, a \in \Sigma\),恰好存在一个 \(p \in K\) 使得 \((q, a, p) \in \Delta\) 时,NFA 就是确定的 (deterministic)

事实上,虽然看起来 NFA DEA 更强大、更通用,但实际上 NFA 总是可以被转换为等价的 DFA。形式上,对于两个有限自动机 \(M_1, M_2\)(无论是 DFA 还是 NFA,当且仅当 \(L(M_1) = L(M_2)\) 时,我们称这两者是等价的(equivalent)。

定理

对于每一个 NFA,存在一个等价的 DFA

证明

对教材 \(P_{69-72}\) 的翻译,略有删改。

\(M=(K,\Sigma,\Delta,s,F)\) 是一个 NFA,我们将构造一个与其等价的 DFA \(M^{\prime}=(K^{\prime},\Sigma,\delta^{\prime},s^{\prime},F^{\prime})\) 。关键思想是将 NFA 看作在任何时刻,不只占据一个状态,而是占据一个状态集合:即,通过到目前为止读取的输入,所有可以从初始状态到达的状态的集合。

以下构造将上述想法形式化:

  • \(M^{\prime}\) 的状态集合 \(K^{\prime}\) 将是 \(2^{K}\),即 \(M\) 的状态集合 \(K\) 的幂集
  • \(M^{\prime}\) 的终态集合 \(F^{\prime}\) 将由 \(K\) 的所有包含至少一个 \(M\) 的终态的子集组成
  • \(M^{\prime}\) 的转移函数 \(\delta^{\prime}\) 的定义会稍微复杂一些,基本思想是:\(M^{\prime}\) 在读取输入符号 \(a \in \Sigma\) 上的移动,模仿 \(M\) 在输入符号 \(a\) 上的移动,可能随后跟随 \(M\) 的任意数量的 e- 移动

为了形式化这个想法,我们需要一个特殊的定义:对于任何状态 \(q \in K\),令 \(E(q)\) \(M\) 的所有可从状态 \(q\) 到达且无需读取任何输入的状态集合。也就是说: \(\(E(q)=\{p\in K:(q,e)\vdash_{M}^{*}(p,e)\}\)\)

换句话说,\(E(q)\) 是集合 \(\{q\}\) 在关系 \(\{(p,r):\text{there is a transition }(p,e,r)\in\Delta\}\) 下的闭包。因此,\(E(q)\) 可以通过以下算法计算:

Initially set E(q) := {q};
while there is a transition (p, e, r) in Delta with p in E(q) and r not in E(q) do:
    E(q) := E(q) union {r}

这个算法是我们用于闭包计算的一般算法的特化 (specialization)。它保证在最多 \(|K|\) 次迭代后终止,因为 while 循环的每次执行都会向 \(E(q)\) 中添加一个新状态,而最多只有 \(|K|\) 个状态可以被添加。

现在准备形式化地定义与 \(M\) 等价的确定性自动机 \(M^{\prime}=(K^{\prime},\Sigma,\delta^{\prime},s^{\prime},F^{\prime})\)。具体来说:

\[ \begin{aligned} K^{\prime}&=2^{K} \\ s^{\prime}&=E(s) \\ F^{\prime}&=\{Q\subseteq K:Q\cap F\ne\emptyset\} \end{aligned} \]

对于每个 \(Q\subseteq K\) 和每个符号 \(a\in\Sigma\),定义: \(\(\delta^{\prime}(Q,a)=\bigcup\{E(p):p\in K\mathrm{~and~}(q,a,p)\in\Delta\text{ for some }q\in Q\}\)\)

也就是说,\(\delta^{\prime}(Q,a)\) 被视为 \(M\) 可以通过读取输入 \(a\)(并且可能随后跟着若干 e- 转移)所能到达的所有状态的集合。

剩下的任务是要证明 \(M^{\prime}\) 确定性的并且等价于 \(M\)

  • 证明 \(M^{\prime}\) 是确定性:注意到 \(\delta^{\prime}\) 是单值的,并且根据其构造方式,它在所有 \(Q\in K^{\prime}\) \(a\in\Sigma\) 上都是良好定义的\(\delta^{\prime}(Q,a)=\emptyset\) 对于某些 \(Q\in K^{\prime}\) \(a\in\Sigma\) 并不意味着 \(\delta^{\prime}\) 不是良好定义的;\(\emptyset\) \(K^{\prime}\) 的一个成员

  • 证明 \(M\) \(M^{\prime}\) 是等价的

    • 我们现在声称:对于任何字符串 \(w\in\Sigma^{*}\) 和任何状态 \(p,q\in K\)

      \[(q,w)\vdash_M^*(p,e)\text{ if and only if }(E(q),w)\vdash_{M^{\prime}}^*(P,e)\]

      对一些包含 \(p\) 的集合 \(P\) 成立。

    • 由此定理将很容易得出:考虑任意字符串 \(w\in\Sigma^{*}\)。那么 \(w\in L(M)\) 当且仅当 \((s,w)\vdash_{M}^{*}(f,e)\) 对于某个 \(f\in F\) (根据定义,当且仅当 \((E(s),w)\vdash_{M^{\prime}}^{*}(Q,e)\) 对于某个包含 \(f\) \(Q\)(根据上述声称;换句话说,当且仅当 \((s^{\prime},w)\vdash_{M^{\prime}}^{*}(Q,e)\) 对于某个 \(Q\in F^{\prime}\)。最后一个条件是 \(w\in L(M^{\prime})\) 的定义。

    • 我们通过对 \(w\) 进行归纳来证明这个声称:

      • 基础步骤:对于 \(|w|=0\)(即 \(w=e\),我们必须证明 \((q,e)\vdash_{M}^{*}(p,e)\) 当且仅当 \((E(q),e)\vdash_{M^{\prime}}^{*}(P,e)\) 对于某个包含 \(p\) 的集合 \(P\)。第一个陈述等价于说 \(p\in E(q)\)。由于 \(M^{\prime}\) 是确定性的,第二个陈述等价于说 \(P=E(q)\) \(P\) 包含 \(p\);即 \(p\in E(q)\)。这就完成了基础步骤的证明。
      • 归纳假设:假设该声称对于所有长度为 \(k\) 或更短的字符串 \(w\) 成立,其中 \(k\ge0\)
        • 对于“仅当”方向,假设 \((q, w)\vdash_{M}^{*}(p,e)\)。那么存在状态 \(r_{1}\) \(r_{2}\) 使得

          \[(q,w)\vdash_{M}^{*}(r_{1},a)\vdash_{M}(r_{2},e)\vdash_{M}^{*}(p,e)\]

          也就是说,\(M\) 从状态 \(q\) 到达状态 \(p\),经过若干次移动(读取了输入 \(v\),随后一次移动(读取了输入 \(a\),随后若干次移动(未读取任何输入。现在 \((q,va)\vdash_{M}^{*}(r_{1},a)\) 等同于 \((q,v)\vdash_{M}^{*}(r_{1},e)\),并且因为 \(|v|=k\),根据归纳假设,\((E(q),v)\vdash_{M^{\prime}}^{*}(R_{1},e)\) 对于某个包含 \(r_{1}\) 的集合 \(R_{1}\) 成立。由于 \((r_{1},a)\vdash_{M}(r_{2},e)\),存在一个三元组 \((r_{1},a,r_{2})\in\Delta\),因此根据 \(M^{\prime}\) 的构造,\(E(r_{2})\subseteq\delta^{\prime}(R_{1},a)\)。又因为 \((r_{2},e)\vdash_{M}^{*}(p,e)\),可以得出 \(p\in E(r_{2})\),所以 \(p\in\delta^{\prime}(R_{1},a)\)。因此,\((R_{1},a)\vdash_{M^{\prime}}(P,e)\) 对于某个包含 \(p\) \(P\) 成立,从而 \((E(q),va)\vdash_{M^{\prime}}^{*}(R_{1},a)\vdash_{M^{\prime}}(P,e)\)

        归纳步骤:我们证明该声称对于任何长度为 \(k+1\) 的字符串 \(w\) 成立。设 \(w=va\),其中 \(a\in\Sigma\),且 \(v\in\Sigma^{*}\)

        • 为了证明另一个方向,假设 \((E(q),va)\vdash_{M^{\prime}}^{*}(R_{1},a)\vdash_{M^{\prime}}(P,e)\),对于某个包含 \(p\) \(P\) 和某个 \(R_{1}\) 使得 \(\delta^{\prime}(R_{1},a)=P\)。现在根据 \(\delta^{\prime}\) 的定义,\(\delta^{\prime}(R_{1},a)\) 是所有集合 \(E(r_{2})\) 的并集,其中对于某个状态 \(r_{1}\in R_{1}\)\((r_{1},a,r_{2})\) \(M\) 的一个转移。由于 \(p\in P=\delta^{\prime}(R_{1},a)\),存在某个特定的 \(r_{2}\) 使得 \(p\in E(r_{2})\),并且对于某个 \(r_{1}\in R_{1}\)\((r_{1},a,r_{2})\) \(M\) 的一个转移。那么根据 \(E(r_{2})\) 的定义,\((r_{2},e)\vdash_{M}^{*}(p,e)\)。同时,根据归纳假设,\((q,v)\vdash_{M}^{*}(r_{1},e)\),因此 \((q, va)\vdash_{M}^{*}(r_{1},a)\vdash_{M}(r_{2},e)\vdash_{M}^{*}(p,e)\)

证毕。

例子

现在利用前面证明过程中给出的算法,将上面的 NFA 转换为等价的 DFA。

  • 由于 \(M\) \(5\) 个状态,因此 \(M'\) \(2^5 = 32\) 个状态
  • 当然其中只要部分状态和 \(M'\) 的运算相关,那些无法从 \(s'\) 到达的状态就是不相关的操作
  • \(E(q)\)

    • \(E(q_0) = \{q_0, q_1, q_2, q_3\}\)
    • \(E(q_1) = \{q_1, q_2, q_3\}\)
    • \(E(q_2) = \{q_2\}\)
  • 因为 \(s' = E(q_0)\),所以 \((q_1, a, q_0), (q_1, a, q_4), (q_3, a, q_4)\) 都是对 \(q \in s'\) 的转移 \((q, a, p)\),即 \(\delta(q, a) = E(q_0) \cup E(q_4) = \{q_0, \dots, q_4\}\)

  • 同理 \((q_0, b, q_2), (q_2, b, q_4)\) 都是对 \(q \in s'\) 的转移 \((q, b, p)\),即 \(\delta(q, b) = E(q_2) \cup E(q_4) = \{q_2, \dots, q_4\}\)
  • 重复上述计算,可得到:

    \[ \begin{aligned}\delta^{\prime}(\{q_0,q_1,q_2,q_3,q_4\},a)&=\{q_0,q_1,q_2,q_3,q_4\},\\\delta^{\prime}(\{q_0,q_1,q_2,q_3,q_4\},b)&=\{q_2,q_3,q_4\},\\\delta^{\prime}(\{q_2,q_3,q_4\},a)&=E(q_4)=\{q_3,q_4\},\\\delta^{\prime}(\{q_2,q_3,q_4\},b)&=E(q_4)=\{q_3,q_4\},\\\delta^{\prime}(\{q_3,q_4\},a)&=E(q_4)=\{q_3,q_4\},\\\delta^{\prime}(\{q_3,q_4\},b)&=\emptyset,\\\delta^{\prime}(\emptyset,a)&=\delta^{\prime}(\emptyset,b)=\emptyset.\end{aligned} \]

对应的状态图如下:

可以看到 \(\{q_0, q_1, q_2, q_3, q_4\}, \{q_2, q_3, q_4\}, \{q_3, q_4\}\) 是最终状态。

评论区

如果大家有什么问题或想法,欢迎在下方留言~