regular-language - 使用泵送引理的条件 3 证明不规则性

Question

所以，我一直在阅读 Sipser 的《计算理论》一书，其中一个练习是:

Let B be the language {0^n1^n | n≥0}.

Prove B is not regular.

本书继续给出证明，使用泵引理，令 s=0^p 1^p，s=xyz 并测试所有三种情况；当y只有0、只有1、0和1时。但我无法理解后两个选项如何通过泵引理 |xy|≤p 的条件三成为可能。这个条件是不是意味着 y 只能是 0？

Answer 1

Does this condition not imply that y can only be 0's?

不，不一定。修复p，并让字符串为

w = xyz = 0^{1/2 p}1^{1/2 p}

是什么阻止x成为第一个字符，z成为最后一个字符，以及y成为中间的所有字符？