Используя условие 3 насосной леммы доказать неправильность

Question

Итак, я шел через книгу Sipser по теории вычислений, и один из упражнений:

Пусть В языке {0^n1^n | n≥0}.

Доказательство B не является регулярным.

Книга продолжает давать доказательство, используя лемму накачки, давая s = 0^p 1^p, s = xyz и проверяя все три случая; когда y - только 0, только 1, 0 и 1. Но я не могу понять, как возможны последние два варианта по условию три из леммы накачки |xy|≤p. Не означает ли это условие, что y может быть только 0?

Answer 1

Это условие не означает, что y может быть только 0?

Нет, не обязательно. Закрепить р, и пусть строка будет

ш = хуг = 0 ^{1/2 р 1/2 р}

Что мешает х быть первым символом, г является последним, и y находится между тем?