形式语言与自动机理论-04-正则语言与有限状态自动机

这一章给出两个重要的结论:

  1. 对于任何正则语言来说,存在识别其的有限状态自动机

  2. 存在识别该语言的有限状态自动机的语言为正则语言

正则表达式到有限自动状态机

首先给出正式的正则表达式的定义。表达式 \(E\) 为正则表达式,当且仅当以下条件之一成立:

  1. \(E = \emptyset\)

  2. \(E = \varepsilon\)

  3. \(E = \alpha \quad (\alpha \in \Sigma)\)

假设 \(E_1, E_2\) 为正则表达式,

  1. \(E = E_1 + E_2\)

  2. \(E = E_1 \cdot E_2\)

  3. \(E = E_1^*\)

以上归纳地定义了正则表达式,由于根据此定义,以子表达式构成偏序关系并且此偏序关系是良基的。

于是给定任意正则表达式(及该表达式描述的正则语言),有如下算法构造性地证明存在识别该语言的有限状态自动机。

  1. 自动机 \(\to \bigcirc \quad \circledcirc\) 识别由 \(E = \emptyset\) 描述的正则语言

  2. 自动机 \(\to \bigcirc \stackrel{\varepsilon}{\to} \circledcirc\) 识别由 \(E = \varepsilon\) 描述的正则语言

  3. 自动机 \(\to \bigcirc \stackrel{\alpha}{\to} \circledcirc\) 识别由 \(E = \alpha \quad (\alpha \in \Sigma)\) 描述的正则语言

注意到上述情况下,该算法构造出的自动机具有以下性质:

  1. 有且仅有一个接受状态,并且该接受状态不为起始状态

  2. 没有进入起始状态的转移

  3. 没有离开终止状态的转移

于是对于其余的情况,假设 \(\varepsilon\)-NFA \(M_{E_i}\) 识别由正则表达式 \(E_i\) 描述的语言(\(i = 1,2\)),且任何 \(M_i\) 皆具有以上性质,于是对于余下的情况,有:

  1. 自动机 \(M_{E_1+E_2} = (Q_{E_1+E_2}, \Sigma, \delta_{E_1+E_2}, q_{0,E_1+E_2}, Q_{acc, E_1+E_2})\) 识别语言 \(E_1 + E_2\)

    其中有

    \[ \begin{aligned} Q_{E_1+E_2} &= Q_{E_1} \uplus Q_{E_2} \uplus \{q_{0,E_1+E_2}, q_{acc, E_1+E_2}\} \\ Q_{acc, E_1+E_2} &= \{q_{acc, E_1+E_2}\} \\ \delta_{E_1+E_2} &= \delta_{E_1} \uplus \delta_{E_2} \uplus \begin{Bmatrix} (q_{0,E_1+E_2}, \varepsilon, q_{0,E_1}) \\ (q_{0,E_1+E_2}, \varepsilon, q_{0,E_2}) \\ (q_{acc,E_1}, \varepsilon, q_{acc,E_1+E_2}) \\ (q_{acc,E_2}, \varepsilon, q_{acc,E_1+E_2}) \end{Bmatrix} \end{aligned} \]

    1

    根据运算 \(\uplus\) 的定义,不失一般性地,有 \(q_{0, E_1+E_2}, q_{acc, E_1+E_2} \not\in Q_{E_1}, Q_{E_2}\)

  2. 自动机 \(M_{E_1 \cdot E_2} = (Q_{E_1 \cdot E_2}, \Sigma, \delta_{E_1 \cdot E_2}, q_{0,E_1 \cdot E_2}, Q_{acc, E_1 \cdot E_2})\) 识别语言 \(E_1 \cdot E_2\)

    其中有

    \[ \begin{aligned} Q_{E_1 \cdot E_2} &= Q_{E_1} \uplus Q_{E_2} \\ Q_{acc, E_1 \cdot E_2} &= \{q_{acc, E_2}\} = Q_{acc, E_2}\\ q_{0,E_1 \cdot E_2} &= q_{0,E_1}\\ \text{令 } q_{acc, E_1} &= q_{0, E_2} \\ \end{aligned} \]

    其中最后一个构造等价于添加状态转移 \((q_{acc, E_1}, \varepsilon, q_{0, E_2})\).

  3. 自动机 \(M_{E_1^*} = (Q_{E_1^*}, \Sigma, \delta_{E_1^*}, q_{0,E_1^*}, Q_{acc, E_1^*})\) 识别语言 \(E_1^*\)

    其中有

    \[ \begin{aligned} Q_{E_1^*} &= Q_{E_1} \uplus \{q_{0,E_1^*}, q_{acc, E_1^*}\} \\ Q_{acc, E_1^*} &= \{q_{acc, E_1^*}\} \\ \delta_{E_1^*} &= \delta_{E_1} \uplus \begin{Bmatrix} (q_{0,E_1^*}, \varepsilon, q_{0,E_1}) \\ (q_{acc,E_1}, \varepsilon, q_{acc,E_1^*}) \end{Bmatrix}\\ \text{令 } q_{acc, E_1} &= q_{0, E_1} \end{aligned} \]

根据结构归纳法可以证明,上述情况中构造出来的自动机皆满足前述条件,于是构造要求的假设成立。因此该算法构造性地证明,对于任何正则语言来说,存在识别其的有限状态自动机。

有限自动状态机到正则表达式

我们给出三种方法

状态消除

我们对状态转移图做出拓展,允许以正则表达式标记转移。如此一来,符合先前定义的状态转移图依然是合法的,因为以字符 \(\sigma \in \Sigma\) 标记的转移可被视为以正则表达式 \(\sigma\) 标记的转移。

接下来根据前文给出的算法移除 \(\varepsilon\)-转移,然后反复进行状态消除程序:

  1. 消除没有从初始状态开始的路径的状态,消除没有路径到达任何一个接受状态的状态

  2. 消除所有自循环,即对于所有 \(q \in Q\),若存在由正则表达式 \(E\) 标记的转移 \((q, E, q) \in \delta\),不失一般性地假设 \(q' \not\in Q\),修改这样的转移为 \((q, E^*, q')\)

    同时若有 \(q \in Q_{acc}\),令 \(q \not\in Q_{acc}\), \(q' \in Q_{acc}\)

    并且若对于某些 \(q_{out} \in Q\) (此时一定有 \(q_{out} \ne q\)),存在由正则表达式 \(E\) 标记的转移 \((q, E, q_{out}) \in \delta\),修改这样的转移为 \((q', E, q_{out})\)

  3. 合并所有分支,即对于所有 \(q_1, q_2 \in Q\),替换所有由正则表达式 \(E_1, E_2\) (\(E_1 \ne E_2\)) 标记的转移 \((q_1, E_1, q_2), (q_1, E_2, q_2)\)\((q_1, E_1 + E_2)\).

  4. 对于所有 \(q_1, q_2, q_3 \in Q\),若有 \(q_2 \in Q_{acc}\),及转移 \((q_1, E_1, q_2), (q_2, E_2, q_3)\),则构造状态 \(q_2'\) 并假设 \(q_2' \not\in Q\),令 \(q_2' \in Q_{acc}\), \(q_2 \not\in Q_{acc}\),构造转移 \((q_1, E_1, q_2')\).

    此时由于进行了第 2 步,于是不可能有 \(q_1, q_3 = q_2\),然而允许 \(q_1 = q_3\).

  5. 对于所有 \(q_1, q_2, q_3 \in Q\),替换所有转移 \((q_1, E_1, q_2), (q_1, E_2, q_2)\)\((q_1, E_1E_2)\).

    类似上一步,不可能有 \(q_1, q_3 = q_2\),然而允许 \(q_1 = q_3\),同时根据上一步有 \(q_2 \not\in Q_{acc}\).

此时返回步骤 1 重复,直到在某一轮迭代中没有移除任何状态及转移。如此得到的状态转移图具有以下性质:

  1. 步骤 5 保证了图里不存在长度多于 1 的路径

  2. 步骤 2 及上一条性质保证了不存在循环

  3. 步骤 3 保证了任何状态至多只有一个输入转移

  4. 步骤 1 保证了图是 reachable 且 co-reachable 的,即没有多余的状态

如此得到的转移图将是深度为 1 的树,且有且仅有所有叶子节点为接受状态。于是将所有转移上的正则表达式以 \(+\) 连接,则可得到描述给定状态机识别的语言的正则表达式。

注意,状态消除程序中每一步骤中可能会有多个匹配的结构。不同的顺序并不保证可以得到相同的正则表达式,然而这些表达式都是等价的。需要注意的是,每一个步骤中的操作应同步进行,即同时移除所有匹配的结构。

以上对状态消除程序的描述适合方便直观理解其原理的目的,然而并不精确。对于使用可变数据结构的程序来说,为达到上述注意中所要求的同步需要额外的工作。

传递闭包

该方法原理上与上一个方法类似,这里给出严谨的描述。

\(NFA\) 的状态依一定次序编号为 \(\{q_1, \dots, q_n\}\),于是得到对状态转移图的矩阵描述 \(T_{n \times n}\):

\[ T_{i, j} = \begin{cases} \varepsilon, &i = j \\ \delta(i, j), &\delta(i, j)! \\ \text{未定义}, &\text{除以上情况外} \end{cases} \]

定义 \(T^k_{i,j}\)\(q_i\) 仅途径 \(\{q_1, \dots, q_k\}\) 到达 \(q_j\) 的路径得到的正则表达式。显然有 \(T^1 = T\)

于是依照如下递归关系求 \(T^n\)

\[ T^k_{i,j} = T^{k-1}_{i,j} + T^{k-1} \cdot (T^{k-1}_{k,k})^* \cdot T^{k-1}_{k,j} \]

\(T^n_{1,1}\) 为所求正则表达式。

注意到以上表达式描述的是一个动态编程的模式,因此虽然描述上使用的是数学语言,其可轻易以编程实现。

Brzozowski 代数方法

除此以外,Brzozowski, Janusz. (1964). Derivatives of Regular Expressions. J. ACM. 11. 481-494. 10.1145/321239.321249. 给出了代数上的方法。避开使用上述文献中正则表达式导数的概念,本文对 Brzozowski 代数方法描述如下。

\(M = (Q, \Sigma, \delta, q_0, Q_{acc})\) 为不含 \(\varepsilon\)-转移 的 NFA,对应于每一个 \(q_i \in Q\) 的方程

\[ Q_i = \sum_{\exists\sigma\in\Sigma, q_j \in Q. q_i \stackrel{\sigma}{\to}q_j} \sigma Q_j + \begin{cases} \{\varepsilon\}, &q_i \in Q_{acc}\\ \emptyset, &\text{否则} \end{cases} \]

形成一个线性方程组。

使用 \(+\), \(\cdot\) 的结合性, \(+\) 对于 \(\cdot\) 的分配性,以及 Arden 引理如下:

\(L,U,V \subseteq \Sigma^*\) 为正则语言,其中有 \(\varepsilon \not\in U\),那么有

\[ L = UL + V \iff L = U^*V \]

解得 \(Q_0\) 为描述状态机 \(M\) 所识别语言的正则表达式。

正则语言的封闭性

由以上结论可以证明正则语言在布尔运算下的封闭性。

\(R\), \(S\) 为正则语言,那么以下语言皆为正则语言:

  1. \(R \cup S\)

    描述该语言的正则表达式为 \(R + S\).

  2. \(\overline{R} = (\Sigma^* - R)\)

    给定识别语言 \(R\) 的 DFA \(M_R\),可构造识别 \(\overline{R}\) 的自动机依下述方法:

    补全 \(M\) 的状态转移函数,即添加状态 \(q_{rej} \in Q_{\overline{R}}\) 并定义所有未定义的转移至 \(q_{rej}\):

    \[ \delta_{\overline{R}}(q, \sigma) = \begin{cases} \delta_R(q, \sigma), &\delta_R(q, \sigma)!\\ q_{rej}, &\text{否则} \end{cases} \]

    然后对于所有 \(q \in Q_R\), 令 \(q \in Q_{acc, \overline{R}} \iff q \in Q/Q_{acc, R}\) (即 \(q \in Q_{\overline{R}}/Q_{acc,\overline{R}} \iff q \in Q_{acc, R}\))。注意此时会有 \(q_{rej} \in Q_{acc, \overline{R}}\).

    于是以前述方法可从自动机 \(M_{\overline{R}}\) 得到描述语言 \(\overline{R}\) 的正则表达式。实践中,描述 \(R\)\(\overline{R}\) 的正则表达式常常区别极大,并且对于有简短正则表达式描述的语言 \(R\) 来说,描述 \(\overline{R}\) 的正则表达式十分复杂的情况也是非常常见的。由此我们可以看出使用有限状态自动机描述正则语言在处理这样的问题时的优越性。

  3. \(R \cap S\)

    可由双重否定率及德摩根律得到 \(R \cap S = \overline{\overline{R} \cup \overline{S}}\) 并且依前述方法得到后者的正则表达式。

    类似上一点的评论,描述 \(R \cap S\) 的正则表达式通常来说与 \(R\), \(S\) 的正则表达式也不见得会有相似之处。这主要是由于识别 \(R \cap S\) 的状态机根本上是通过不确定的方式并行运行分别识别 \(R\), \(S\) 的两个自动机所导致。

由于 2 和 3 证明的正则性的的封闭性,我们没有必要拓展正则表达式至有表达补与交的能力 2,因此实践中常常利于位于更低级别系统中的排中律及合取介入率来识别给定正则语言的交及补。


  1. 定义中缀二元运算 \(A \uplus B := A \cup B\),并且不失一般性地,该运算保证断言 \(A \cap B = \emptyset\) 成立。理解上可认为 \(A \uplus B \simeq A \times \{0\} \cup B \times \{1\} =: A \sqcup B\)↩︎

  2. 术语上称补与交运算对于已定义的运算来说不是正交的,即他们所表达的意义可由已有的运算定义出来↩︎