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

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

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

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

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

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


regular-language proof automata pumping-lemma
person n00b1990    schedule 14.03.2013    source источник
comment
Пара вопросов для уточнения: являются ли + и = частью алфавита L, а не математическими вычислениями? Означает ли # (x) двоичное значение x?   -  person DPenner1    schedule 14.03.2013
comment
Извините, я забыл сказать, что такое алфавит и что на самом деле означает #. Я только что отредактировал вопрос.   -  person n00b1990    schedule 14.03.2013
comment
@ n00b1990 Этот язык даже не контекстно-свободные языки (CFL) Прочтите мой ответ Дайте мне знать, если вам понадобится дополнительная помощь.   -  person Grijesh Chauhan    schedule 15.03.2013
comment
@ n00b1990 Я забыл сказать, что в связанном вопросе вы можете найти доказательство для обычного языка   -  person Grijesh Chauhan    schedule 15.03.2013
comment
@ n00b1990 Я могу предположить, что должна быть длина накачки P и что для всего w элемента L, что LENGTH(w) >= P, но Почему? прочтите one и два   -  person Grijesh Chauhan    schedule 15.03.2013
comment
@ GrijeshChauhan, извините, я имел в виду, что если вы хотите доказать с помощью леммы о накачке, что язык не является регулярным, вы доказываете это от противного. Я должен был написать: «Предположим, что язык правильный. Тогда должна быть длина накачки P и для всех w элементов L, что LENGTH (w) ›= P. Верно?   -  person n00b1990    schedule 16.03.2013

Ответы (2)


arrow_upward
2
arrow_downward

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

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

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

Доказательство (в спойлере):

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

person DPenner1    schedule 14.03.2013
comment
Огромное спасибо за помощь. Теперь я понимаю. Поскольку уравнение не должно изменяться, это означает, что наше предположение о том, что язык является регулярным, неверно и, следовательно, он должен быть нерегулярным. Теперь я понял, спасибо! Молодцы со спойлером :) - person n00b1990; 15.03.2013
comment
Хотя мне очень любопытно. Как узнать, легче ли выбрать класс строк, чем одну строку? А что было бы, если бы b действительно содержало + or =? Разве этого не было бы достаточно, чтобы прийти к противоречию и, следовательно, к доказательству? - person n00b1990; 15.03.2013
comment
Что касается выбора класса струн, мне было немного проще, потому что мой мыслительный процесс был таков: теперь мне нужно накачать b так, чтобы число изменилось. И b, которые всегда удовлетворяют, это те, у которых нет начальных нулей. Итак, теперь, когда я это знал, мне действительно не нужно было искать конкретную строку, это был бы просто дополнительный шаг. Однако, как и @ Patrick87, выбор конкретной строки по-прежнему полностью действителен и, в зависимости от вашего мыслительного процесса, может быть проще. - person DPenner1; 15.03.2013
comment
Если b содержит + or =, тогда, когда вы перекачиваете строку для i = 2 (или больше), b будет содержать 2 (или больше) + or =. Следовательно, w не будет на языке. Однако для доказательства этого недостаточно. Это противоречие в конкретном случае, когда b имеет + or =, но случай, когда b не содержит + or =, все равно должен быть рассмотрен. - person DPenner1; 15.03.2013
comment
Разве вы не сказали бы это, потому что мы нашли строку abc с b, содержащую + или =, что лемма о перекачке не работает? Лемма о перекачке проверяет, есть ли в языке новая перекачиваемая строка. Ну, как вы говорите, если бы b содержал, например, +, и вы качаете несколько i greater then 1, тогда b будет содержать более одного +. Следовательно, мы нашли строку, которой нет на языке. Лемма о перекачке говорит, что каждая перекачиваемая строка должна быть на языке, поэтому мы пришли к выводу, что язык не должен быть регулярным. Разве этого не должно быть достаточно для доказательства? Или я что-то упускаю? - person n00b1990; 16.03.2013
comment
Да, каждая перекачиваемая струна должна быть на языке ... проблема в том, что строка w, а не b. На самом деле мы не знаем, что содержит b, поскольку лемма о перекачке гарантирует только существование деления w = abc. Мы не знаем, что это за деление, поэтому мы должны рассмотреть все возможные деления и, следовательно, все возможные b. Короче говоря, для одной строки w (или класса, как я сделал в моем доказательстве) вы должны рассмотреть все возможные b. - person DPenner1; 16.03.2013

arrow_upward
2
arrow_downward

Выберите в качестве строки 1(0^n+1) + 1(0^n) = 11(0^n).

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

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

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

person Patrick87    schedule 14.03.2013
comment
Я частично понимаю ваше объяснение, но можете ли вы мне сказать, зачем нужна эта строка? Или это класс струн? я ценю вашу помощь - person n00b1990; 15.03.2013
comment
@ n00b1990 Это класс строк на вашем языке, для которого лемма о перекачке не работает. Доказательства с использованием леммы о накачке обычно выглядят следующим образом: лемма о накачке говорит, что все строки определенной длины должны быть прокачиваемыми; вот строка как минимум этой длины; не перекачивается; предположение, что язык удовлетворяет лемме о накачке, неверно; язык не регулярный. - person Patrick87; 15.03.2013