0

我对抽水引理相对较新,我在这里有一个问题,我认为我回答正确,谁能告诉我这是否有效,如果无效,为什么不

问题:{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 中是可行的,所以我的泵引理是错误的。

4

1 回答 1

0

我不相信您的答案有效,因为无法确定 wwww 不在该语言中。

例如,让 |w| 是一个倍数 3(即 3*k 对于某些 k)所以你的原始字符串是长度:|3k|+|3k|+|3k|=9*3k

因此,如果您添加另一个字符串长度为 3k。长度现在是 12k,也是 3 的倍数。

尝试类似:让 w = 100...001,其中 p 个零被 1 包围。那么无论你如何抽 10..0110..0110..01 uvw ,你都会脱离语言。

于 2014-05-09T21:49:25.383 回答