自动机理论

自动机包含状态机$S$和状态转移函数$\delta$

根据计算/表达能力的不同，自动机包含多个层次。其中用于词法分析的是有限状态机。

词法分析的目标是通过正则表达式RE生成确定性有穷自动机DFA，进而生成词法分析器的代码。

NFA

非确定性有穷状态机$A$是一个五元组$A = (\Sigma ,S,s_0,\delta,F)$

• 字母表$\Sigma$
• 有穷的状态集$S$
• 唯一的初始状态$s_0\in S$
• 状态转移函数$\delta:S\times (\Sigma \cup {\epsilon})\rightarrow 2^S$
• 接受状态集合$F\subseteq S$

约定所有没有对应出边的字符默认指向一个不存在的“空状态”$\phi$。

例如对于以下的状态机

有以下的状态转换

NFA可以识别一个$\Sigma$上的一个字符串，结果为接受或拒绝。

$A$接受字符串$x$，当且仅当存在一条从开始状态$s_0$到某个接受状态$f\in F$，标号为$x$的路径。

于是$A$定义了一种语言$L(A)$，即能接受的字符串的集合。

DFA

确定性有穷状态机$A$是一个五元组$A = (\Sigma ,S,s_0,\delta,F)$

• 字母表$\Sigma$
• 有穷的状态集$S$
• 唯一的初始状态$s_0\in S$
• 状态转移函数$\delta:S\times \Sigma\rightarrow S$
• 接受状态集合$F\subseteq S$

约定所有没有对应出边的字符默认指向一个不存在的“死状态”。

对于以上的NFA，转换为DFA则为

转换

NFA适合描述语言，但不易计算；DFA适合计算，但不易描述。

RE到NFA

RE到NFA使用的是汤普森构造法，即按结构归纳。

由于正则表达式由四条规则定义，因而我们可以通过为每条规则定义NFA来实现构造。

$\epsilon$是正则表达式

$a\in \Sigma$是正则表达式

$N((s))=N(s)$

如果$s,t$是正则表达式，则$s\mid t$是正则表达式

根据开始两条归纳假设，$N(s),N(t)$的初始和终止状态都是唯一的。

如果$s,t$是正则表达式，则$st$是正则表达式

如果$s$是正则表达式，则$s^*$是正则表达式

NFA到DFA

NFA到DFA使用的子集构造法。使用DFA模拟NFA，即将NFA中每一次转换的目标集合作为DFA的一个状态。例如对于以上的NFA，可以构造出以下状态：

其中包含终止状态的集合就是DFA的一个终止状态。

• 从状态s开始，只通过$\epsilon$转移可达的状态集合$\epsilon-closure(s)={t\in S_N\mid s\rightarrow^{\epsilon^*}t}$
• 对于状态集$T$，有$\epsilon-closure(T)=\bigcup_{s\in T}\epsilon-closure(s)$
• 在状态集$T$上接受一个字符$a$的移动$move(T,a)=\bigcup_{s\in T}\delta(s,a)$

对于转换前的NFA $N:(\Sigma_N,S_N,n_0,\delta_N,F_N)$和转换后的DFA $D:(\Sigma_D,S_D,d_0,\delta_D,F_D)$，我们有$\Sigma_D=\Sigma_N$，$S_D\subseteq 2^{S_N}(\forall s_D\in S_D: s_d\subseteq S_N)$

得到的DFA的初始状态$d_0=\epsilon-closure(n_0)$

转移函数$\forall a\in \Sigma_D :\delta_D(s_D,a)=\epsilon-closure(move(s_D,a))$

接受状态集$F_D={s_D\in S_D\mid \exist f\in F_N,f\in s_D}$

DFA最小化

通过子集构造法的结果复杂度是指数级的，需要对结果进行化简。即将等价状态进行合并。

等价状态的定义：

但是这个定义是递归的，而应用时没有递归的起始条件可以使用。在实际中采用划分的方式，利用以上定义的否命题来对不等价的状态进行划分，而接受状态和非接受状态必定不等价，形成初始情况。

最初，令$\Pi_{new}=\Pi$

for($\Pi$中的每个组G，且还可以划分){

​ 将G划分为更小的组，使得两个状态s和t在同一小组中当且仅当对于所有的输入符号a，状态s和t上 的转换都到达$\Pi$中的同一组。

​ 将$\Pi_{new}$中将G替换为对G进行分划得到的那些小组。

}

最终，将同一等价类的状态合并。