形式语言与自动机

南京大学2025-2026秋季学期课程

[Formal Languages and Automata]:课程主页

引言

1.自动机可以理解为检测一种形式化语言的工具，通过用节点表示状态，用边表示状态的迁移，最简单的是确定性有穷状态机，状态有限，根据输入的内容确定性进行状态迁移。

“最终”和”接受“两个状态：自动机接受一个语言的字符串，如果最终停止的状态节点是被接受的，那么这个状态是终止状态，终止状态是可以有出边的，因为可能有没读完的字符串。

有穷状态机

非确定性有穷自动机 NFA

非确定性有穷自动机：对于确定性有穷自动机，可以理解为一个棋子在地图上走路，当前所处位置和下一次接受的输入，唯一地决定了下一个状态；可是非确定性有穷自动机却不一样，非常的有意思，和我一开始理解的不同，并不是根据概率转移（像马尔可夫链一样），而是在接受输入后变为n个确定性有穷状态机，可以理解为一个小队在探险，在某些情况下几人分头行动。

NFA与DFA的等价性

DFA显然是一种NFA，但是从NFA到DFA的构造，我们采用子集构造法（一种在计算机科学领域常用的证明方法）。

对于一个,要将其转化为一个等价的,

是DFA的状态集合，是的幂集，是所有中元素且与交集不为空集的集合的集合。

子集构造的过程其实就是根据NFA去构造一个等价的DFA，而这个过程的核心要点就是将NFA中的多状态并行转化为状态的集合，将这个集合当作等价DFA的单状态，其实也就是上面所说的，只要这个状态中包含一个终止状态，那么这个状态集合就可以作为DFA的一个终止状态。

NFA到DFA的转移

带转移的NFA

闭包

从初始状态出发，经过一条或多条转移能够到达的状态集合，称为

从NFA到DFA

• DFA的初始状态是NFA初始状态的闭包
• DFA每做一次转移，就要做一次闭包

正则表达式

正则表达式表示了一种语言称为正则语言，这种语言通常是一个字母表所构成的语言的子集。

比如$01^{}+10^{}\lbrace0,1\rbrace$构成字符串集合的子集。

正则表达式的三种操作：

• 并：二者选其一
• 连接：直接拼接
• 克林闭包：任选多个元素重复

从有穷自动机到正则表达式

构造出一种正则语言使得其能够表示DFA中所有的状态迁移。

定理：若存在一个 表示的语言为，则一定存在一种正则表达式使得。

从DFA构造正则表达式：[DFA到等价正则表达式的转化 - jjppp - 博客园]

Arden’s Theorem

形如的方程，的解的形式是的形式，将自动机之间状态的转移视作字符串（正则表达式）的集合的运算。

从有穷自动机到正则表达式的转化只需要将有穷状态机的状态转化为接受正则表达式的集合，然后列线性方程组求解即可。

从正则表达式到有穷自动机

首先为基础的正则表达式，单个字符，构建自动机，然后将自动机组合。

将正则表达式转化为DFA的关键在于：将正则表达式的部分拆分为基础的表达式，然后拼接起来。

，将这个正则表达式转化为DFA。

克林公式的递推性质

但是克林公式只是表示到达一次的，所以如果存在自环需要在后面加上自环的闭包。

正则语言的性质

正则语言的泵引理

设是正则语言，则任意属于的串,存在一个与相关的常数，如果，能够将串分为三个串的形式且满足：

• 对于所有的,串

将使用泵引理证明语言视作一场对抗赛，选手1提出一个语言，选手2选择一个n，选手1根据n构造一个属于L语言的串，选手2根据泵引理将其拆解为，选手1选择k使得不属于语言L，证明L不是正则语言。

• 在最后一步选择k时需要根据实际问题分析

正则语言的封闭性

布尔运算

1.并运算的封闭

2.补运算的封闭

3.交运算的封闭：构造乘积自动机

4.差运算的封闭性：

反转

同态

DFA的等价性和最小化