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

引理 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}}\]

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