寻找两两可区分字符串集验证素数k对应2^k拼接非正则语言

语言定义明确 #

• 语言L的所有元素均仅由字符2构成，任意字符串属于L当且仅当它可以拆分为前后两个全2子串，且每个子串的长度都是素数，即$L = { 2^p \circ 2^q \mid p、q均为素数 }$，其中$\circ$代表字符串拼接。

核心依据 #

Myhill-Nerode定理规定：两个字符串$x$、$y$相对于语言$L$可区分的充要条件是，存在后缀字符串$z$，使得$xz \in L$和$yz \in L$的真假性相反。如果能构造出无限大小的两两可区分字符串集合，即可直接证明$L$不是正则语言。

具体构造方案 #

• 我们选取集合 S = { 2^n | n 为任意正整数 }，显然$S$是无限集合。
• 对$S$中任意两个不同的字符串$x=2^a$、$y=2b$，不妨设$a < b$，可按如下步骤构造区分后缀$z$：
  1. 选取素数$k$，使得$k + (b-a)$为合数（素数有无穷多个，这样的$k$必然存在）
  2. 令后缀$z = 2^{k + 2 - a}$，即$z$是长度为$k+2-a$的全2字符串
  3. 此时$xz$的总长度为$a + (k+2-a) = k + 2$，$k$和$2$都是素数，因此$xz$必然属于$L$
  4. $yz$的总长度为$b + (k+2-a) = 2 + (k + b - a)$，由于$k + b -a$是我们预先选好的合数，而奇数要拆分为两个素数之和必须包含唯一的偶素数$2$，剩下的部分为合数，不满足要求，因此$yz$必然不属于$L$
• 由此可证，$S$中任意两个不同的字符串都满足两两可区分的条件，$S$是无限大小的可区分集合，因此$L$不是正则语言。

内容的提问来源于stack exchange，提问作者amanda gibson