2 Finite Automata¶

说明

本文档仅涉及部分内容，仅可用于复习重点知识
本章 5、6 节考试不考

呃啊，看了半天原来不考

1 Deterministic Finite Automata¶

A deterministic finite automaton is a quintuple \(M = (K,\Sigma, \delta, s, F)\) where

\(K\) is a finite set of states
\(\Sigma\) is an alphabet
\(s \in K\) is the initial state
\(F \subseteq K\) is the set of final states
\(\delta\), the transition function, is a function from \(K \times \Sigma\) to \(K\)

configuration 描述了 DFA 在某个特定时刻的完整快照。一个配置被形式化地定义为 当前状态 和 未读字符串 的有序对，即属于笛卡尔积 \(K \times \Sigma^*\)

二元关系 \(\vdash_M\) 在图灵机 \(M\) 的两个配置之间成立，当且仅当机器可以通过一次移动从一个配置转换到另一个配置。因此，如果 \((q,w)\) 和 \((q',w')\) 是 \(M\) 的两个配置，那么 \((q,w) \vdash_M (q', w')\) 当且仅当存在某个符号 \(a \in \Sigma\)，使得 \(w = aw'\)，并且转移函数满足 \(\delta(q,a) = q'\)。在这种情况下，我们说 \((q,w)\) yields \((q',w')\) in one step

实际上 \(\vdash_M\) 是从 \(K \times \Sigma^+\) 到 \(K \times \Sigma^*\) 的一个函数，也就是说，除了形如 \((q,e)\) 的配置外，每个配置都有唯一确定的下一个配置。形如 \((q,e)\) 的配置表示图灵机 \(M\) 已经消耗完所有输入，因此在此处停止运行

我们将 \(\vdash_M\) 的 reflexive, transitive closure 记作 \(\vdash_M^*\). \((q,w) \vdash_M^* (q', w')\) 被读作 \((q,w)\) yields \((q',w')\)（在若干步（可能是零步）之后生成）

A string \(w \in \Sigma^*\) is said to be accepted by \(M\) 当且仅当存在某个状态 \(q \in F\)，使得 \((s,w) \vdash_M^*(q,e)\)

the language accepted by \(M\), \(L(M)\), is the set of all strings accepted by \(M\)

使用 state diagram 来方便的表示

2 Nondeterministic Finite Automata¶

\(L = (ab\cup aba)^*\) 的 DFA 状态图

这并不容易看懂

其 NFA 的状态图

A nondeterministic finite automaton is a quintuple \(M = (K,\Sigma, \Delta, s, F)\), where

\(K\) is a finite set of states
\(\Sigma\) is an alphabet
\(s \in K\) is the initial state
\(F \subseteq K\) is the set of final states
\(\Delta\), the transition relation, is a subset of \(K \times (\Sigma \cup \lbrace e\rbrace) \times K\)

The relation \(\vdash_M\) between configurations is defined as follows: \((q,w) \vdash_M (q', w')\) if and only if there is a \(u \in \Sigma \cup \lbrace e\rbrace\) such that \(w = uw'\) and \((q,u,q') \in \Delta\)

\(\vdash_M^*\) 同理

由定义可知，DFA 是 NFA 的一种特殊情况

tow finite automata \(M_1\) and \(M_2\) are equivalent if and only if \(L(M_1) = L(M_2)\)

每一个 NFA 都有和它 equivalent 的 DFA

令 \(E(q) = \lbrace p \in K: (q,e) \vdash_M^* (p,e)\rbrace\)

现在定义一个和原状态机 \(M\) 等价的状态机 \(M' = (K',\Sigma,\delta',s',F')\)

\(K' = 2^K\)
\(s' = E(s)\)
\(F' = \lbrace Q \subseteq K: Q \cap F \not ={\emptyset}\rbrace\)
\(\delta'(Q,a)=\bigcup\lbrace E(p):p\in K \ and\ (q,a,p)\in \Delta\ for\ some\ q \in Q\rbrace\)

这就是子集构造法

现在我们构造一个和 Figure 2-9 等价的 FA：

1.定义初始状态 \(s'\)

\(s' = E(q_0) = \lbrace q_0,q_1,q_2,q_3\rbrace\)

2.计算 \(\delta'(s',a)\) 和 \(\delta'(s',b)\)

\(\delta'(s',a) = E(q_0) \cup E(q_4) = \lbrace q_0,q_1,q_2,q_3,q_4\rbrace\)

\(\delta'(s',b) = E(q_2) \cup E(q_4) = \lbrace q_2,q_3,q_4\rbrace\)

3.继续构建其他状态

现在我们已经有了三个状态：

\(s' = \lbrace q_0,q_1,q_2,q_3\rbrace\)
\(A = \lbrace q_0,q_1,q_2,q_3,q_4\rbrace\)
\(B = \lbrace q_2,q_3,q_4\rbrace\)

继续不断计算它们的转移即可，得到

\(C = \lbrace q_3,q_4\rbrace\)
\(\emptyset\)

由于原 NFA 的 \(q_4\) 是最终状态，所以这里的 FA 的最终状态有 \(A,B,C\)

3 Finite Automata and Regular Expressions¶

The class of languages accepted by finite automata is closed under

union
concatenation
Kleene star
complementation
intersection

如果两个语言 \(L_1, L_2\) 都能被某个有限自动机识别（即它们是正则语言），那么通过这些运算得到的新语言也仍然是正则语言。也就是说，正则语言对这些基本运算具有“封闭性”

给定两个 NFA \(M_1, M_2\)

1.union

构造一个新的 NFA \(M\)，使得 \(L(M) = L(M_1) \cup L(M_2)\)

构造方法：

引入一个新的初始状态 \(s\)，该状态不在 \(K_1\) 或 \(K_2\) 中
从 \(s\) 出发，用空转移分别到达 \(M_1\) 和 \(M_2\) 的初始状态 \(s_1\) 和 \(s_2\)
接受状态（final state）集合为 \(F_1 \cup F_2\)
状态转移函数为两个原自动机的并集，并加上新的 \(e\) 转移

2.concatenation

构造一个新的 NFA \(M\)，使得 \(L(M) = L(M_1) \circ L(M_2)\)

先运行 \(M_1\)
一旦 \(M_1\) 到达某个接受状态，就通过 \(e\) 转移到 \(M_2\) 的初始状态 \(s_2\)
然后运行 \(M_2\)

3.Kleene star

构造一个新的 NFA \(M\)，使得 \(L(M) = L(M_1)^*\)

\(M\) 在 \(M_1\) 的基础上增加了一个状态 \(s_1'\)，同时这个状态也是 \(M\) 的初始状态
从 \(s_1'\) 有一个 \(e\) 转移到达 \(s_1\)，从这里运行 \(M_1\)
到达 \(M_1\) 的接受状态后，通过 \(e\) 转移能够回到 \(s_1\)，以便重复运行

4.Complementation

给定一个 DFA \(M = (K,\Sigma,\delta,s,F)\)，其补语言 \(\bar{L} = \Sigma^* - L(M)\) 可以被另一个 DFA \(\bar{M} = (K,\Sigma,\delta,s,K-F)\) 所接受

也就是说 \(\bar{M}\) 和 \(M\) 完全相同，只是终态和非终态互换了一下而已

5.intersection

\(L_1 \cap L_2 = \Sigma^* - ((\Sigma^* - L_1) \cup (\Sigma^* - L_2))\)

可以从 union 和 complementation 中推导出来

A language is regular if and only if it is accepted by a finite automaton

为 Figure 2-15 中的 DFA 所接受的语言构造一个正则表达式：

\(\lbrace w \in\lbrace a,b\rbrace^*: w 包含 3k+1 个 b，其中 k \in N\rbrace\)

简化条件：

只有一个终态，记作 \(F = \lbrace f\rbrace\)
没有进入初始状态 \(s\) 的转移
没有从终态 \(f\) 发出的转移

通过逐步删除中间状态的方式，将 DFA 转换为一个只包含初始状态和终态的状态，并用正则表达式标注边上的路径

将原自动机改写为“特殊形式”——单初态、单终态，无入初态或出终态的转移
编号状态为 \(q_1,q_2,\cdots,q_n\)，设 \(s=q_{n-1},f=q_n\)
目标是求出从 \(q_{n-1}\) 到 \(q_n\) 的所有路径对应的正则表达式，即 \(R(n-1,n,n)\)
使用递推公式计算 \(R(i,j,k)\)：表示从状态 \(i\) 到 \(j\)，途中不经过编号大于 \(k\) 的状态的所有路径组成的语言

1.根据简化条件转换

添加新初始状态 \(q_4\)，新终态 \(q_5\)，使满足简化条件

2.计算 \(R(i,j,1)\)：消除状态 \(q_1\)

现在要消除状态 \(q_1\)，根据算法，我们考虑所有经过 \(q_1\) 的路径，并将其替换为等价的正则表达式

\(q_4 \rightarrow q_1 \rightarrow q_3\): \(ea^*b = a^*b\)
\(q_2 \rightarrow q_1 \rightarrow q_3\): \(ba^*b\)

得到：

3.计算 \(R(i,j,2)\)：消除状态 \(q_2\)

\(q_3 \rightarrow q_2 \rightarrow q_3\): \(ba^*ba^*b\)

得到：

4.消除状态 \(q_3\)

\(q_4 \rightarrow q_3 \rightarrow q_5\): \(a^*b(a \cup ba^*ba^*b)^*\)

最终答案就是 \(a^*b(a \cup ba^*ba^*b)^*\)

4 Languages That Are and Are Not Regular¶

尽管我们现在有很多方法能够证明语言是正则的，但仍然缺乏有效的方法来证明一个语言不是正则的。由于正则表达式的数量是可数无穷的，而语言的总数是不可数无穷的，因此非正则语言是确实存在的

所有正则语言都具备，但某些非正则语言不具备的两个性质：

当一个字符串从左到右被扫描时，为了在最后确定该字符串是否属于某个语言，所需的内存容量必须是有界的、事先固定的，并且仅依赖于语言本身，而不依赖于具体的输入字符串。例如，我们预期语言 \(\lbrace a^nb^n | n \geqslant 0 \rbrace\) 不是正则的，因为很难想象一个有限状态设备（如有限自动机）如何在到达 \(a\) 和 \(b\) 的边界时，准确记住之前看到的 \(a\) 的个数，以便于后面的 \(b\) 的个数进行比较
包含无限多个字符串的正则语言，通常由带有循环的自动机或包含 Kleene star 的正则表达式表示。这类语言必然包含具有某种简单重复结构的无限子集，这种结构来源于正则表达式中的 Kleene star，或有限自动机状态图中的循环。因此，我们可以预期，例如语言 \(\lbrace a^n | n \geqslant 1 \text{且 } n \text{ 是质数} \rbrace\) 不是正则的，因为在质数集合中不存在简单的周期性规律

正则语言能被有限状态自动机识别 → 自动机只有有限个状态 → 记忆能力有限

正则语言的无限部分必须有某种“重复模式”，比如通过循环或 Kleene star 实现

这些都不是严格证明，而是直觉上的理由

Pumping Theorems

Let \(L\) be a regular language. There is an integer \(n \geqslant 1\) such that any string \(w \in L\) with \(|w| \geqslant n\) can be rewritten as \(w = xyz\) such that

\(y \not ={e}\)
\(|xy| \leqslant n\)
\(xy^iz \in L\) for each \(i \geqslant 0\)

如果一个语言 \(L\) 是正则的，那么它的所有足够长的字符串（长度 ≥ 某个常数 \(n\)）都必须包含一段“可泵”的子串 \(y\)，可以重复任意次数，结果仍然在 \(L\) 中

换句话说：正则语言中的长字符串具有某种“循环结构”

proof

一个语言正则 \(\implies\) 满足泵定理
满足泵定理 \(\nRightarrow\) 一个语言正则

* 5 State Minimization¶

考虑上图中的 DFA，它接受语言 \(L = (ab \cup ba)^*\)。考虑状态 \(q_7\)，显然，这个状态 unreachable

这是在任何确定性有限自动机上可以进行的最简单的优化：移除所有不可达状态及其相关的输入和输出转移

设 \(L \subseteq \Sigma^*\) 是一个语言，且 \(x,y \in \Sigma^*\)。我们说 \(x\) 和 \(y\) equivalent with respect to \(L\)，记作 \(x \approx_L y\)，如果对所有 \(z \in \Sigma^*\)，满足：\(xz \in L \text{ 当且仅当 } yz \in L\)

换句话说：\(x \approx_L y\) 当且仅当要么两个字符串都属于 \(L\)，要么都不属于；并且，向 \(x\) 和 \(y\) 后面附加任何固定的字符串 \(z\)，得到的新字符串要么都属于 \(L\)，要么都不属于

我们用 \([x]\) 表示 \(x\) 所属的关于 \(L\) 的等价类

对于 Figure 2-20 中的自动机所接受的语言 \(L = (ab \cup ba)^*\)，有 4 个等价类（或者说，可以分成 4 个等价类）：

\([e] = L\)：满足 DFA 接受状态的字符串
\([a] = La\)：只能通过后接 \(bL\) 才能进入 \(L\) 的字符串
\([b] = Lb\)：只能通过后接 \(aL\) 才能进入 \(L\) 的字符串
\([aa] = L(aa \cup bb) \Sigma^*\)：所有以 \(aa\) 或 \(bb\) 为前缀的字符串（也就是无法进入 \(L\) 的字符串）

设 \(M = (K, \Sigma, \delta, s, F)\) 是一个确定性有限自动机。我们说两个字符串 \(x,y \in \Sigma^*\) equivalent with respect to \(M\)，记作 \(x \sim_M y\)，直观上，它们都能从初始状态 \(s\) 把自动机带到同一个状态。形式上，\(x \sim_M y\) 当且仅当存在某个状态 \(q\)，使得：\((s,x) \vdash_M^* (q,e) \text{ 且 } (s,y) \vdash_M^* (q,e)\)

我们将与状态 \(q\) 对应的等价类记为 \(E_q\)

对于 Figure 2-20 中的自动机，等价类如下：

\(E_{q_1} = (ba)^*\)
\(E_{q_2} = La \cup a\)
\(E_{q_3} = abL\)
\(E_{q_4} = b(ab)^*\)
\(E_{q_5} = L(bb \cup aa) \Sigma^*\)
\(E_{q_6} = abLb\)

For any DFA \(M = (K, \Sigma, \delta, s, F)\) and any string \(x, y \in \Sigma^*\), if \(x \sim_M y\), then \(x \approx_{L(M)} y\)

对于 Figure 2-20 中的自动机

\([e]\) 和 \(E_{q_1}\) \(E_{q_3}\) 对应
\([a]\) 和 \(E_{q_2}\)
\([b]\) 和 \(E_{q_4}\) \(E_{q_6}\) 对应
\([aa]\) 和 \(E_{q_5}\) 对应

The Myhill-Nerode Theorem

设 \(L \subseteq \Sigma^*\) 是一个正则语言。那么存在一个确定性有限自动机，其状态数恰好等于 \(\approx_L\) 的等价类个数，并且该自动机接受语言 \(L\)

对于 Figure 2-20 中的自动机，根据定理，其状态数最少有 4 个

也就是说，状态 \(q_4\) \(q_6\) 等价，\(q_1, q_3\) 等价

The Myhill-Nerode Theorem

A language \(L\) is regular if and only if \(\approx_L\) has finitely many equivalence classes

我们称两个状态 \(p\) \(q\) 是等价的，记作 \(p \equiv q\)，如果对于所有的 \(z \in \Sigma^*\)，\(z\) 都能驱动自动机从状态 \(p\) 或 \(q\) 到达某个接受状态或者到达 trap

称 \(p \equiv_n q\)：对所有长度不超过 \(n\) 的字符串 \(z\)，满足上面的条件

For nay two states \(p, q \in K\) and any integer \(n \geqslant 1\), \(p \equiv_n q\) if and only if

\(p \equiv_{n-1} q\)
for all \(a \in \Sigma\), \(\delta(p,a) \equiv_{n-1}\delta(q,a)\)

对于 Figure 2-20 中的自动机

\(\equiv_0\): \(\lbrace q_1, q_3\rbrace\) \(\lbrace q_2,q_4,q_5,q_6\rbrace\)
\(\equiv_1\): \(\lbrace q_1, q_3\rbrace\) \(\lbrace q_2\rbrace\) \(\lbrace q_4,q_6\rbrace\) \(\lbrace q_5\rbrace\)

接下来没有能够继续分割的了，这样同样能够得到 Figure 2-21

* 6 Algorithms For Finite Automata¶

分析将非确定性有限自动机转换为确定性有限自动机的算法的复杂度：

该算法的输出当中的 \(\delta'(Q,a) = \bigcup\lbrace E(p): p \in K, (q,a,p) \in \Delta \text{ for some } q \in Q \rbrace\)

计算所有的 \(E(p)\)，时间复杂度 \(O(|K|^3)\)
对每个可能的状态子集 \(Q \subseteq K\)（共 \(2^{|K|}\) 个），和每个字母 \(a \in \Sigma\)，计算 \(\delta'(Q,a)\)。每次计算需要遍历 \(\Delta\) 中的边，最多 \(|\Delta|\) 条，每条对应一次 \(E(p)\) 查询。时间复杂度为 \(O(2^{|K|}|\Sigma||\Delta||K|^2)\)

整个算法的总复杂度为 \(O(2^{|K|}|\Sigma||\Delta||K|^5)\)

将正则表达式 \(R\) 转换为 NFA 是非常高效的。状态数最多 \(2|R|\)，转移数最多 \(4|R|^2\)。是一个多项式时间的构造过程

将有限自动机转换为正则表达式。虽然状态数是多项式，但输出的正则表达式长度可能是指数级的，总长度达 \(O(3^{|K|})\)

DFA 最小化算法。最多经过 \(|K| - 1\) 次迭代，总复杂度为 \(O(|\Sigma||K|^3)\)，多项式时间

DFA 的等价性判定。先对两个 DFA 分别做最小化，若最小化后的 DFA 完全相同，则等价。由于最小化是多项式时间，所以整体也是多项式时间

相比之下，我们目前唯一知道的判断两个非确定性有限自动机（NFA）或两个正则表达式是否等价的方法，是先将它们都转换为确定性有限自动机（DFA），然后测试这两个 DFA 是否等价。而这一过程的算法复杂度当然是指数级的

存在一个指数时间算法，给定一个非确定性有限自动机（NFA），可以构造出一个等价的确定性有限自动机（DFA）
存在一个多项式时间算法，给定一个正则表达式，可以构造出一个等价的非确定性有限自动机（NFA）
存在一个指数时间算法，给定一个非确定性有限自动机（NFA），可以构造出一个等价的正则表达式
存在一个多项式时间算法，给定一个确定性有限自动机（DFA），可以构造出一个状态数最少的等价 DFA
存在一个多项式时间算法，给定两个确定性有限自动机（DFA），可以判断它们是否等价
存在一个指数时间算法，给定两个非确定性有限自动机（NFA），可以判断它们是否等价；类似地，也可以用于判断两个正则表达式的等价性

评论区

欢迎在评论区指出文档错误，为文档提供宝贵意见，或写下你的疑问