Может ли кто-нибудь помочь мне с этим доказательством, используя лемму о перекачке?

Question

Я только начал читать о лемме о перекачке и знаю, как выполнить несколько доказательств, главным образом, в противоречии. Только этот конкретный вопрос, на который я, похоже, не нахожу ответа. Я понятия не имею, как начать. Я могу предположить, что должна быть длина откачки P и что для всего элемента w L, что LENGTH(w) >= P. И, конечно, мы можем написать w как xyz с тремя нормальными условиями леммы о перекачке.

Я должен доказательства, что следующий язык не является регулярным:

L = {x + y = z | x,y,z element of {0,1}* and #(x) + #(y) = #(z) } 

Может кто-то помочь мне в этом, я действительно хочу, чтобы освоить процесс в теплоизолирующие такого рода вопросы?

Edit:
К сожалению, забыл сказать, что алфавит {0,1,+,=} и # означает бинарное значение строки. Как #(00101) = 5 и #(110) = 6.

Answer 1

Поскольку вы хотите освоить процесс, я покажу несколько вещей, прежде чем показывать доказательство.

1. Первое, что нужно заметить, что + и = может появиться только один раз. Поэтому, когда вы пишете строку w в w = abc, перекачиваемой части, b, не может содержать + или = иначе вы бы достичь тривиальное противоречие (я не использую более стандартного w = xyz обозначения, чтобы избежать путаницы с определением L «s).

2. Другое дело, что обычно вы выбираете конкретную строку w для перекачки. В этом случае может быть проще выбрать класс строк, которые имеют определенное свойство. Лемма перекачки требует, чтобы вы достигли противоположности, используя одну строку, но нет причин, по которым вы не можете достичь противоречия с несколькими строками.

Proof (в спойлере):

Итак w быть любая строка в L такой, что |w| ≥ P и x, y, z не содержат ведущих 0 «с. По лемме о перекачке можно написать w как w = abc. Подкачкой леммы известно, что b не пусто. Поскольку b не может содержать + или =, он полностью содержится либо в x, y,, либо в z. Накачка w с любыми i ≠ 1 приводит к тому, что бинарное уравнение больше не удерживается, так как ровно один из x, y, z будет другим номером (вот почему нам не нужен был ведущий 0).

Answer 2

Выбрать как строку 1(0^n+1) + 1(0^n) = 11(0^n).

Другими словами, ваша строка будет читать «сумма двух до мощности n + 2 плюс два с мощностью n + 1 равна 11, за которой следуют n нулей».

Поскольку строка, подлежащая накачке, будет состоять целиком из символов из первого сложения, накачка должна изменить представленное число (добавление или удаление цифр на число изменит число, это верно, потому что наша строка не содержит ведущих нули), и если x + y = z имеет место, то x' + y = z не выполняется, если x' != x (по крайней мере, целых чисел).

Так как для леммы о перекачке требуется, чтобы на языке перекачки были введены строки, а перекачка этой строки не удалась, мы имеем, что язык не является регулярным.