子集构造法

思想

使用DFA去模拟DFA

简单构造例子

首先0,1,2,4,7是$ϵ$立刻转移的目的，因此无法区分，以此作为初始状态。

• 遇到a可以转移到3,8，遇到$ϵ$转移到6,7,1,4,2，因此一共可以转移到3,8,6,7,1,4,2
  • 再遇到a可以转移到3,6,7,1,2,4,8和上一次一样
  • 再遇到b可以进入5,6,7,1,2,4,9
• 同理，遇到b可以转移到5,6,7,1,2,4
  • 再遇到a可以到达：3867142
  • 再遇到b可以到达：567124，为自身
• 一直进行下去，直到终止状态（这里是到达10）

闭包

在一个集合上判断

不断地对集合做运算，直到无论如何做运算，运算结果都等于自身，即$F(x)=x$，此时将x称作f的不动点

$T⟹f(T)⟹f(f(T))⟹f(f(f(T)))⟹\dots$

$ϵ$闭包

$$ϵ\text{-closure }(T)=\bigcup _{s\in T}ϵ\text{-closure }(s)$$ $$ϵ\text{-closure }(T)=\bigcup _{s\in T}ϵ\text{-closure }(s)$$ $$\mathrm{move}(T,a)=\bigcup _{s\in T}\delta (s,a)$$

原理

$$N:({\Sigma }_N,S_N,n_0,{\delta }_N,F_N)$$ $$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)$$

• 初始状态：$d_0=ϵ$-closure$(n_0)$
• 转移函数：$\forall a\in {\Sigma }_D:{\delta }_D(s_D,a)=ϵ$-closure(move$(s_D,a))$
• 接受状态集：$F_D=\{s_D\in S_D\mid \exists f\in F_N.f\in s_D\}$

复杂度分析

$$|S_N|=n$$ $$|S_D|=\Theta (2^n)$$

最坏情况下，$|S_D|=\Omega (2^n)$

复杂例子

长度 $m\ge n$个字符的$a,b$串，且倒数第$n$个字符是$a$

此时$L_n=(a|b{)}^{\ast }a(a|b)$