Понять лемму прокачки

Question

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

Проблема: {www | w is {a,b}*}

Мой подход:

L = www

u * (v ^ k) * w должно быть подмножеством L

WWW

| | |

UVW

uvw = www

(u)(v ^ 2)(w) = wwww

wwww не является частью языка www и поэтому не является регулярным

Редактировать: Ну, в соответствии с моим пониманием лемму прокачки, взяв "тестовую строку", на которую мы смотрим, и разделив ее на часть, которая остается такой же, за которой следует повторяемая часть, а затем, наконец, еще одна часть, которая остается прежней. В моем "подходе" я взял тестовую строку "www" и разделил ее на u, v и w, каждая из которых, соответственно, содержит одну букву "w", где v - повторяемая секция, а две другие - те, которые остаются неизменными. Я удваиваю раздел v и получаю в результате uvvw, который переводится как wwww, который выглядит так, как будто он не является частью языка www. У меня хорошее чувство, что я ошибаюсь из-за условия "w is {a,b}*", которое, как мне кажется, включает в себя пустую строку, и поскольку пустая строка является жизнеспособной в wwww и www, моя лемма прокачки неверна. Я просто хотел бы знать, какой подход я бы использовал для решения такой проблемы, это просто проблема практики

Answer 1

Я не верю, что ваш ответ работает, потому что нет никакого способа убедиться, что wwww не на языке.

Например, пусть | w | быть кратным 3 (т.е. 3*k для некоторого k). Таким образом, ваша оригинальная строка имеет длину: |3k|+|3k|+|3k|=9*3k

Так что если вы добавите еще одну строку длиной 3 КБ. Длина теперь 12k, что также кратно 3.

Попробуйте что-то вроде: Пусть w = 100...001, где у вас есть нули, заключенные в 1 с. Тогда независимо от того, как вы прокачаете 10..0110..0110..01 uvw, вы будете вне языка.