关于利用无限语言F构造愚弄集证明L非正则的思路求助

Hey，你找对方向啦！用F构造愚弄集/结合Myhill-Nerode定理确实是破题的关键，我给你拆解下具体思路：

• 先锚定核心定理：正则语言的Myhill-Nerode等价类数量必然有限。如果能证明L有无限多个这样的等价类，那直接就能推出L非正则——这其实比硬凑愚弄集更顺，而且和你手里的F的特性完美匹配。
• 结合题目给的F的条件：对F中任意不同的$x$、$y$，存在$w$、$z$使得$wxz \in L$且$wyz \notin L$。这直接说明$x$和$y$不属于同一个Myhill-Nerode等价类！因为等价类的定义是「两个字符串在所有上下文（前缀+后缀）下的接受性完全一致」，现在我们找到了一个具体的上下文（$w$作为前缀，$z$作为后缀）能区分$x$和$y$，那它们肯定不在同一个等价类里。
• 既然$F$是无限语言，那$L$的Myhill-Nerode等价类数量也必然是无限的，结论自然就出来了：$L$不是正则的。

如果你一定要构造出具体的愚弄集，那也可以从上面的逻辑转化：

• 对于每个$x \in F$，我们取题目中对应区分$x$和其他元素的前缀$w$（或者你固定每个$x$配对一个专属的$w_x$），构造集合$S = { w_x x \mid x \in F }$。
• 对$S$中任意两个不同的元素$s_x = w_x x$和$s_y = w_y y$，根据题目条件，存在$z$使得$s_x z \in L$且$s_y z \notin L$（或者反过来）——这完全满足愚弄集的定义：任意两个不同元素都能被某个后缀$z$区分接受性。
• 因为$F$是无限的，所以$S$也是无限愚弄集，而正则语言不可能有无限的愚弄集，因此$L$非正则。

备注：内容来源于stack exchange，提问作者Irene