Покажите, что L = {ww^R : w ∈ Σ*} не является регулярным, используя лемму о накачке.

Если я позволю строке w быть a^mb^m, то мы знаем, что y будет состоять только из a из-за правила |xy| <= m.

И если я установлю i=0, то ww^R будет иметь меньше a с левой стороны, чем с правой. Таким образом, это доказывает, что этот язык не является регулярным.

Однако в моем учебнике (Введение в формальные языки и автоматы, стр. 118, Линц) говорится, что если бы я выбрал w = a^2m и позволил y = aa, то потерпел бы неудачу.

Но как так?

На мой взгляд, независимо от того, что такое x, y, z, у первого a^2m будет меньше a или больше, в зависимости от того, что такое i, чем у второго a^2m.


regex regular-language pumping-lemma
person Mint.K    schedule 27.02.2016    source источник
comment
Я голосую за то, чтобы закрыть этот вопрос как не относящийся к теме, поскольку он принадлежит math.stackexchange.com или cs.stackexchange.com.   -  person timgeb    schedule 28.02.2016
comment
@timgeb, это определенно не место на математическом обмене. Вы можете поспорить за CS, но не за математику ИМХО. Речь идет о формальных языках.   -  person ChiefTwoPencils    schedule 28.02.2016
comment
@ChiefTwoPencils И что? Мы все еще говорим о математическом доказательстве. Граница между теоретической информатикой и математикой очень размыта. Вы действительно хотите разместить его на linguistics.stackexchange.com?   -  person timgeb    schedule 28.02.2016
comment
Нет, я уже предложил альтернативное место, если это уместно. Эта книга, тема и задача не основаны на математике, несмотря на то, что это математическое доказательство. Он основан на теории вычислений и является стандартным курсом в учебной программе по информатике. Чтобы доказать это, нужно было бы понять правила; правила, которым вряд ли учат математиков (просто предположение). @тимгеб   -  person ChiefTwoPencils    schedule 28.02.2016

Ответы (1)


arrow_upward
1
arrow_downward

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

Для любого m >= 1 у вас есть aa[aa...]. Таким образом, когда ваш оппонент выбирает y = aa, он заставляет вас внедрить строку из L в w(i). Независимо от того, сколько раз он был перекачан, если вообще, вы получите: (aa)^k : k = pumps, что является строкой в ​​L

Я думаю, что использовать только a — плохой выбор. Наличие двух символов алфавита обычно облегчает выигрыш. Как продолжает говориться в книге, вы не можете предполагать, что победить вашего противника должно быть легко; любые попытки автоматически становятся недействительными.

person ChiefTwoPencils    schedule 27.02.2016
comment
Пусть k = 0, а m = 3. Тогда аааааа аааааа. Я устанавливаю x = a, y = aa в первых 6 a и z в остальных. Если я прокачу y 0 раз. Строка становится aaaa aaaaaa. Что не равно ww^R. В первом w на 2 буквы меньше. Я делаю что-то неправильно? - person Mint.K; 28.02.2016
comment
@ M.Kim, я думаю, твоя проблема может заключаться в том, кто что выбирает. См. (3) в примере 4.7 на 117. Оппонент выбирает m и разложение xyz. Вы выбираете w до того, как я выберу разложение. Кроме того, да, у нас было четное количество баллов, и мы убрали четное их количество. У нас все еще есть четное количество букв "а". Мы не говорим о сторонах; нас интересует, находится ли строка в L или нет. - person ChiefTwoPencils; 28.02.2016
comment
@ M.Kim, вот почему использовать (a ^ m) (b ^ m) так просто. (a^m)(b^m)(b^m)(a^m) можно рассматривать как стороны, поскольку мы позволяем им иметь дело только с a на одной стороне ( стороны разделены буквой b). Таким образом, если я добавлю или удалю какие-либо буквы a, это не выполнит предположение, потому что я не могу компенсировать это на другом конце (у меня было бы (a^(mk))(b^2m)(a^m) : ( м - к) ‹ м). Неправда, когда вы делаете это так просто с одним символом и четным количеством общих символов. Это вообще помогает? - person ChiefTwoPencils; 28.02.2016
comment
да, это помогает, и я понимаю, что он продолжает генерировать четное количество a. Однако по длине обе стороны должны быть одинаковыми, хотя они могут содержать все четное количество букв «а». Поскольку L = ww^R, |w| и |w^R| должны быть одинаковыми, верно? Но если я возьму четное количество a (y) слева, как эта строка все еще находится в L? - person Mint.K; 28.02.2016
comment
@ М.Ким, я не вижу этого ограничения. Прошло некоторое время, но я думаю, что вы слишком строги. В книге выбрано w = w(w^R) = xyz = (a^m)(b^2m)(a^m), поэтому мы смотрим на общую строку. Мы выбираем любой w в L и хотим увидеть, находится ли любой w(i) в L. Таким образом, вместо того, чтобы рассматривать ваш пример, где i=0, как aaaa aaaaaa, посмотрите на него как на aaaaaaaaaaa, который находится в Л. - person ChiefTwoPencils; 28.02.2016
comment
да теперь я понял. Я был слишком строг, рассматривая это как стороны. Глядя на это как на целую строку, определенно имеет смысл. Спасибо - person Mint.K; 28.02.2016
comment
@М.Ким. Рад помочь. Не помогает то, что в доказательстве вы выбираете w, который не совпадает с w в этом определении языка. - person ChiefTwoPencils; 28.02.2016