正则语言在可列个并和交运算下的不封闭性

在$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}}$$

根据前一部分的说明，该结果不一定是正则语言。