正则语言在可列个并和交运算下的不封闭性
引理 Myhill–Nerode定理
在$L \subset \Sigma^{*}$上定义等价关系。
$\forall x, y \in L$ 若$x=y$则有$\forall w \in \Sigma^*$,$xw \in L, yw\in L$同时成立或同时不成立。
记该等价关系为$R$
若$|L/R| < \infty$当且仅当$L$是正则语言。
可列个正则语言的并
定义
字符集$\Sigma = {0,1}$
字符串集合满足以下递推式
$S_{i} = S_{i-1}0^{i}1$
初始条件为
$S_{0}=1$
可以简单列一下前几个
$S_{1}=101,S_{2}=101001,S_{3}=1010010001$
显然一个有限长的字符串形成的集合一定是正则语言。
考虑$\large S = \bigcup_{i=0}^{\infty}{S_{i}}$
显然$S_{i} \neq S_{j}, \forall i\neq j$
则$|S/R| = \aleph_{0}$,故由Myhill-Nerode定理,$S$不是正则语言。
可列个正则语言的交
不妨记各个正则语言为$S_{i}$
根据De Morgan`s law
$$\large S = \bigcap_{i=0}^{\infty}S_{i} = \bigcup_{i=0}^{\infty}\overline{S_{i}}$$
根据前一部分的说明,该结果不一定是正则语言。