pumping-lemma - 我是否正确应用了泵引理？

Question

L = { w | w in {0,1}* and w has equal number of 0s and 1s }

令 n 为抽水引理的数量。

我选择 s = 0ⁿ 1ⁿ 和 y = 0^t 其中 1 <= t <= n。

给出 xyz = 0^(n-t) 0^t 1ⁿ= 0ⁿ 1 ⁿ 在 L 中。

但是 xz = 0^(n-t) 1ⁿ 不在 L. 矛盾中。

我应用正确吗？

Answer 1

嗯……你差一点!那里。就在最后一条语句中，您没有抽取字符串 w = xyz在 y .

现在我们首先假设 L 是正则的，其中 L = { w | w in {0,1}* and w has equal number of 0s and 1s }然后我们将继续证明对于任何 i >= 0 pumped string 即 w = xyⁱz 不包含相同数量的 0 和 1(矛盾 per se) 因此，语言不规则:

L 由 :

L = {0ⁿ1ⁿ | n >= 0}

如果 y = 0^t => w = 0^n-t0^t1ⁿ

现在在为 i >= 0 抽取 y 之后我们得到

xyⁱz = 0^n-t0^it1ⁿ

-> xyⁱz = 0^n+(i-1)t1ⁿ

现在，由于 n+(i-1)t 不等于 n，这与我们关于 L = { w | w in {0,1}* and w has equal number of 0s and 1s } 的假设相矛盾因此 xyⁱz 不属于 L

注意-您还需要考虑其他情况，例如 y = 0^t1¹ , y = 1 ^t 等等，后来证明这些确实蕴含着矛盾。