3 NFA转DFA

问题：用计算机很难在 NFA 上跑模拟看串 $x$ 是否会被接受（需要回溯）。

子集构造法可以将一个 NFA 转换成 DFA。

首先需要给出一些函数方便下面使用：

1. $\varepsilon\text{-closure}(s):=c(s)$，从状态 $s$ 出发，只用 $\varepsilon$ 转换能达到的状态集合。
2. $\varepsilon\text{-closure}(T):=c(T)=\cup_{s\in T}c(s)$，相当于从一个状态集合能达到的所有状态集合的并。
3. $\text{move}(T,a):=m(T,a)=\cup_{s\in T} m(s,a)$，把 $\text{move}(s,a)$ 拓展成 $T$ 的多态函数。

输入的 NFA 所有可能的输入字母表记为 $\Sigma$；

输出的 DFA 的状态集合记为 $D_S$，对应的转换表记为 $D_T$。

初始状态：$D_S=\{c(s_0)\}$，$s_0$ 是 NFA 的开始状态，并且尚未标记（在这里，标记以 $^*$ 记） $$ \begin{aligned} &\textbf{while }(D_S\text{有未被标记的状态}T):\newline &\quad\quad T=T^*;\newline &\quad\quad \textbf{for }(\text{符号}a\text{ : }\Sigma):\newline &\quad\quad\quad\quad U=c(m(T,a));\newline &\quad\quad\quad\quad D_T[T,a]=U;\newline &\quad\quad\quad\quad \textbf{if }(U\not\in D_S):\newline &\quad\quad\quad\quad\quad\quad D_S=D_S\cup U;\newline \end{aligned} $$

例题

假设有如下的转换图：

$X$ 是开始状态，按算法步骤来一步一步走

$S$ in $D_S$	$m(S,a)$	$c(m(S,a))$	$m(S,b)$	$c(m(S,b))$
$A:\{X,1,2\}$	{1}	$B:\{1,2\}$	{1, 3}	$C:\{1,2,3\}$
$B:\{1,2\}$	{1}	$B$	{1, 3}	$C$
$C:\{1,2,3\}$	{1, Y}	$D:\{1,2,Y\}$	{1, 3}	$C$
$D:\{1,2,Y\}$	{1}	$B$	{1, 3}	$C$

非常容易出错，出错的点在于：

• $m(S,a)$ 表示从 $S$ 的状态出发，能够到达的状态集合，而非有 $a$ 出边的 $S$ 状态集合。
• 在计算 $c(T)$ 时，一个状态自身也可以通过 $\varepsilon$ 转换到自身，所以总是有 $m(S,a)\subseteq c(m(S,a))$。

根据上面得到的表，就可以确定得出的 DFA 了。

并且，可以看出，假设有 $n$ 个可能的输入字符，这个表就有 $2n+1$ 列，手动画工作量是很大的。（~~球球考试别让我手算~~）

本文阅读量