我对抽水引理相对较新,我在这里有一个问题,我认为我回答正确,谁能告诉我这是否有效,如果无效,为什么不
问题:{www | w 是 {a,b}*}
我的做法:
L = www
u* (v^k) * w 必须是 L 的子集
万维网
| | |
紫外线
紫外线 = 万维网
(u) (v^2) (w) = wwww
wwww 不是语言 www 的一部分,因此不是常规的
编辑:好吧,根据我的理解,抽引引理通过采用我们正在查看的“测试字符串”并将其拆分为一个保持相同的部分,然后是一个可重复的部分,最后是另一个保持不变的部分。在我的“方法”中,我将测试字符串“www”拆分为 u、v 和 w,每个分别持有一个“w”,其中 v 是可重复部分,另外两个是保持相同的部分。我将 v 部分加倍,最后得到一个结果 uvvw,它转换为 wwww,看起来好像它不是语言 www 的一部分。我有一种很好的感觉,我错了,因为我认为包括空字符串的条件“w is {a,b}*”,并且由于空字符串在 wwww 和 www 中是可行的,所以我的泵引理是错误的。