RPR: Formal Languages and Automata
Published:
by
Bo Fu
- Categories:
- RPR-Review-for-Postgraduate-Recommendation 4
- 形式语言与自动机篇 Formal Languages and Automata
- 开始之前 Before All
- 通论 Intro part
- 有限自动机 Finite Automata（FA）
- 正则表达式 Regular Expression（RE）
- 下推自动机 PushDown Automata（PDA）
- 上下文无关语言 Context-Free Language（CFL）
- 图灵机 Turing Machine（TM）
- 可判定性和计算复杂性 Decidability and Complexity
- 迁移系统 Transition System（TS）
- Petri网 Petri Nets（PN）
- 时间自动机 Timed Automata（TA）
- 其他 Ending
开始之前，你可能需要看一下有关此系列博客的介绍 RPR: Before All. Introduction 。
形式语言与自动机篇 Formal Languages and Automata
开始之前 Before All
所用教材为Introduction to Automata Theory, Languages, and Computations，，复习跟随 NJU 形式语言与自动机（一般简称为FLA）课程（上学期刚学的，还有印象，应该能很快拾起来）。
这篇文章可能涉及很多形式定义，这并不违背我博客的初衷，因为我认为形式语言与自动机的本质就在于严格定义、严格应用。
（不知道为什么，但还是复习 FLA 复习的爽）
通论 Intro part
-
A study of abstract models of computers and computation.
这门课主要研究抽象的计算机与计算模型。
-
Undecidable and Intractable Problems.
不可判定问题与难问题。
重点在于形式化（Formalism），严格就是一切。
有限自动机 Finite Automata（FA）
有穷自动机（FA） 泛讲
- 形式系统；只能记住有穷的信息量；信息通过当前状态记录和转换；状态按照当前输入进行固定转移。
- 其重要性在于对正则语言类进行转化和表达，可以说只要用到了正则语言的地方就可以将其与有穷自动机联系来理解分析。
- 例如编译原理中的词法分析阶段，便可以使用这一工具进行识别操作。
- The set of strings accepted by an automaton $A$ is the language of $A$, which is named as $L\left(A\right)$.
- 注意语言就是字符串的集合，我个人更倾向于它想要描述的是什么串在集合内，什么串没有这样的信息。
- 字母表（Alphabet $\Sigma$），字符（String），字符串长度，空串（$\varepsilon$，长度为零的串）
- Subtlety: Context determines the type.
- 不同语境下相同表达的不同含义，这个其实没什么道理，就当学习一些“黑话”行话，在特定语境使用相应的表达即可。
- 语言（Language: defined as subset of $\Sigma^{*}$）
确定性有穷自动机 Deterministic FA（DFA）
DFA is defined as a formalism for defining languages, consisting of $\left(\mathrm{Q}, \Sigma, \delta, q_{0}, \mathrm{F}\right)$:
- $\mathrm{Q}$：状态集合；$\Sigma$：输入字母表；$\delta$：迁移函数（$\mathrm{Q}\times \Sigma\to \mathrm{Q}$）；$q_{0}$：初始状态；$\mathrm{F}$：接受（最终）状态的集合。
- “Final” and “accepting” are synonyms.
- 注意，这里的迁移函数 $\delta$ 在理想状态或者原则下应该是全函数，但是如果出现有空缺，那么我们可以创造一个死状态（dead state）来补全定义。
- DFA 的图表示法：节点表示状态，有向边表示迁移函数。
对迁移函数的扩展（Extended Transition Function），本质就是改变其定义域从而达到 $\hat{\delta}:\mathrm{Q}\times \Sigma^{*} \to \mathrm{Q}$，定义使用归纳定义（Induction Definition）。
- 根据字符串长度进行归纳，$\hat{\delta}\left(q,\epsilon\right)=q$ 以及相应地归纳 $\hat{\delta}\left(q,wa \right) = \delta \left(\hat{\delta}\left(q,w \right),a\right)$。
DFA 定义的语言就是使得 $\hat{\delta}\left(q_ {0}, w\right)\in \mathrm{F}$ 的字符串 $w$ 的集合。
- \[L\left(A\right) := \left\{w\mid \hat{\delta}\left(q_ {0}, w\right)\in \mathrm{F}\right\}\]
如何证明某个 DFA 接受的语言就是所描述的特定字符串集合？
- 两部分，要同时证明正确性与安全性，即 $S\subseteq T$ 与 $T\subseteq S$。
- 一般来说，都要采用归纳性证明，另一方面重点也在于证明某个状态满足某种性质。
FA 对应的语言类 正则语言 Regular Languages
正则语言的一种定义是：一个语言能被 DFA 接受，那么这个语言就是正则的（Regular）。
- 注意，这里的接受指的是有且仅有这个语言内的字符串可以被此 DFA 接收（一定是充要的）。
那我们为什么要划分正则语言这样一个语言类？直觉上讲，应该是因为有非正则语言。非正则语言的最经典例子就是
\[\left\{0^ {n}1^ {n}\mid n\in \mathbb{N}\right\}\]- 其证明可以使用反证法＋状态有限性证明，也可以直接用接下来要介绍的泵引理来证明。
但是同样，既然我们划分出这样一个类，那也一定有很多正则语言，值得注意的是，所有有穷语言都是正则的。
- 其他的例子还包括回文串、模等价类等。
非确定性图灵机 Nondeterministic FA（NFA）
引入了不确定性，在形式定义中只改变了 $\delta$ 的定义，使其定义为 $\delta:\mathrm{Q}\times \Sigma\to2^{\mathrm{Q}}$，也即将迁移定义在状态集合的子集中，满足要求时可能会走到不同的状态。
同样，对 NFA 的迁移函数我们也可以作类似 DFA 的扩展，唯一的变化时将直接的函数复合变为了所有可能集合的并。
转换 Transformation between DFA & NFA
DFA 到 NFA 的转换非常简单，将迁移函数的元素解释为单元素集合即可。
NFA 到 DFA 的转换使用子集构造法（Subset Construction）。
- 关键在于理解这句话：新 DFA 的状态是以原状态的集合形式出现的，迁移可以理解为集合间的概率性可转移。
-
具体的懒得写了，每次看到这里都大概过一遍就行，不要忘了起始状态是
\[q_ {0}':=\left\{q_ {0}\right\}\] -
等价性证明，归纳证明对于任意字符串 $w$ 都有
\[\hat{\delta}_ {N} \left(q_ {0} , w\right) = \hat{\delta}_ {D} \left(\left\{q_ {0} \right\}, w \right)\]即可。
带空转移的 NFA
允许状态间的 $\epsilon$ 转移，更方便表达，所以一般来说 NFA 都默认带空转移，表达的语言类仍为正则语言。
重要的相关分析概念是状态闭包（Closure of States）。
- $CL\left(q\right)$ represents the set of states you can reach from state $q$ following only arcs labeled $\varepsilon$.
- 可以这样理解，到达状态 $q$ 本质上其实到达了 $CL\left(q\right)$ 这个状态集合。
转换 Transformation between NFA & $\varepsilon$-NFA
NFA 到 $\varepsilon$-NFA 的转换非常简单，直接解释为一个不带空转移的 $\varepsilon$-NFA 即可。
$\varepsilon$-NFA 到 NFA 的转换，直接利用 $CL\left(q\right)$ 的概念重写迁移函数就行了，唯一记住一点，在能用空转移的时候都闭包一下就可以了，在此基础上等价性证明也是比较容易的，几乎显而易见。
总结
DFA，NFA 和 $\varepsilon$-NFA 可以相互转换，表达的语言类完全等价。
- 三者之中，显见 $\varepsilon$-NFA 最容易理解，同时也要记住，只有 DFA 是可实际实现的。
（实际上，正则表达式的识别器就是用转化为 DFA 的形式来实现的，在这个意义上其实挺实用的）
正则表达式 Regular Expression（RE）
定义
Regular expressions describe languages by an algebra.
本质上，是构成了一个从表达式类到正则语言类的满映射。
- 为什么这里我强调了满映射？那这是单射吗？可以思考一下。
前置知识：字符串上的操作
- 拼接（concatenation）、星闭包（Kleene star）
- 字符串集合的并
定义使用归纳定义，以单字符字符串单元集、空串集、空集为归纳基础，以上介绍的拼接、星闭包和集合并为归纳过程，最后以此定义出正则表达式。
- 操作符的优先级从高到低为星闭包、拼接和集合并。
正则表达式和有穷自动机的等价性
- RE to FA.
- 使用 $\varepsilon$-NFA，思考为什么？最灵活（the most powerful）
证明使用归纳证明（这其实早已扎根于 RE 的定义，毕竟其本身就是使用归纳定义的）。
首先构造出三种归纳基础的自动机，再根据三种不同操作进行构造，此处不再赘述。
- FA to RE.
- 使用 DFA，为什么？行为最显现、最固定（the most restrictive）
同样，使用归纳，具体使用 $k$-path 来进行证明，这里的 $k$-path 定义类似于（或者说其实完全等价于）Floyd 算法的思路，限制了路径中的最大点标号，但对终点无限制，因此我们可以说某点到某点的 $k$-path，而对于此处的归纳证明，归纳基础很简单，最重点的就是如下的归纳公式：
\[\mathrm{R}_{ij}^{k} = \mathrm{R}_{ij}^{k-1} + \mathrm{R}_{ik}^{k-1} \left(\mathrm{R}_{kk}^{k-1}\right)^{*}\mathrm{R}_{kj}^{k-1}\]最终，此 DFA 对应的 RE 可以表示为 $\mathrm{R}_ {ij} ^{k}$，其中 $i,j$ 分别为起始状态和终止状态，如果有多个终结状态，直接将各个对应的 RE 相并即可。
结果 这样的证明意义是什么
Each of the three types of automata (DFA, NFA, $\varepsilon$-NFA) we discussed, and regular expressions as well, define exactly the same set of languages: the regular languages.
我们之前证明过 $\text{DFA}\leftrightarrow \text{NFA}\leftrightarrow \text{$\varepsilon$-NFA}$，现在又证明了 $\text{RE}\rightarrow\text{$\varepsilon$-NFA}$ 以及 $\text{DFA}\to \text{RE}$，因此可以说这几个有穷自动机以及正则表达式之间都是等价的关系，都等价地表达正则语言类这个语言类。
- 怎么说，感觉就是因为这样的结论，才让正则语言的理论看起来如此和谐美丽。
正则语言的可判定性
可判定性：什么是可判定性
A decision property for a class of languages corresponds an algorithm that takes a formal description of a language (e.g., a DFA) and tells whether or not some property holds.
- Example: Is language L empty?
简单来说，判定某个形式语言的某个性质是否存在。
正则语言的可判定性
The Membership Problem 成员属问题
- 根据对应的输入直接跑一遍对应的 DFA 就行了，输入字符串有穷则模拟过程一定有穷。
The Emptiness Problem 判空问题
- 计算 Reachability，如果至少有一个终止状态是从初始状态可达的，那么语言非空。
The Infiniteness Problem 无穷问题
-
Key idea: if the DFA has $n$ states, and the language contains any string of length $n$ or more, then the language is infinite.
也就是说，考虑是否包含一个长度超过 DFA 自身状态数的字符串，如有则说明形成环（有一个状态在路径上重复出现了至少两次），因此语言一定无穷。
- 与泵引理有异曲同工之妙。
- 其实可以写作充要条件，另一方面更好证。
-
Second key idea: if there is a string of length $> n$ ($=$ number of states) in $L$, then there is a string of length between $n$ and $2n-1$.
- 用泵引理其实可以直接证明，或者采用证明泵引理的思路，考虑 the first cycle 即可。
-
由此，我们便有了一个有限的检测区间，直接枚举就已是一个标准的解决算法了
-
Better: find cycles between the start state and a final state.
判定是否有环更好，例如用拓扑排序判环即可。
-
Equivalence 判定两个语言是否等价
- 构造积DFA并设定终止状态为差状态再判断其对应的语言是否非空。
- 本质上是判断 $\left(L_ {1}\setminus L_ {2}\right) + \left(L_ {2}\setminus L_ {1}\right)$ 是否为空。
Containment 判断语言间的包含关系
- 同样是积DFA，唯一的改变就是改变终止状态的设置，使得判其是否空等价于判断 $\left(L_ {1}\setminus L_ {2}\right)$ 是否单边为空。
泵引理 The Pumping Lemma
泵引理（正则版）是非常重要的性质，通常用来证明某个语言的非正则性。
For every regular language $L$, there is an integer $n$, such that for every string $w$ in $L$ of length $> n$ we can write $w = xyz$ such that:
- \[\left|xy\right|<n\]
- \[\left|y\right|>0\]
- For all $i\in\mathbb{N}$, $xy^{i}z\in L$.
- 使用泵引理的实践经验：认真考虑对谁使用，一般跟 $n$ 有关系，另外就是考虑清楚泵进还是泵出。
最小 DFA
The Minimum-State DFA for a Regular Language
-
算法关键在于不同状态是否可区分这样一个性质，计算出一个表格，若有不可区别的状态则合并，当所有状态可相互区分时，DFA状态数最小。
-
证明：当所有状态可相互区分时，DFA状态数最小。
反证 + 得出一定存在不可区分状态（相悖）。
-
计算过程使用递归法。
-
合并不可区分状态前后记得删去不可达状态（本身就没用）。
-
正则语言的封闭性
封闭性也经常用来证明某个语言的归属性，因为其本身肯能并不好证明，但是其在封闭保持运算后的结果很有可能容易证明，在此情况下，我们也可以通过反证法证得其本身的归属性。
显然在正则语言定义的三种基本操作符（集合并、星闭包、拼接）下可以保持封闭。
- 将语言用 RE 形式表示即可
Closure Under Intersection 集合交下的封闭性
- 构造积DFA并设定终止状态为两个原状态都是终止状态的积状态。
Closure Under Difference 差运算下的封闭性
- 同样积DFA并设定终止状态为被差状态是终止状态而差状态不是的积状态。
Closure Under Complementation 补运算下的封闭性
- $L^{C} = \Sigma^{*}-L$，差封闭因此补封闭。
Closure Under Reversal 逆运算下的封闭性
- 根据逆定义新的正则表达式即可（思考）。
Closure Under Homomorphism 同态运算下的封闭性
- 相当于直接改 RE 了。
Closure Proof for Inverse Homomorphism 逆同态运算下的封闭性
-
构造新的DFA并根据原DFA的状态构造出转移函数（先同态过去再应用扩展后的转移函数）。
-
证明的关键在于归纳证明式子：
\[\delta_{B} \left(q_{0} , w\right) = \delta_{A} \left(q_{0} , h\left(w \right)\right)\]