Q: Доказательство прокачки леммы

Question

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

L1 = {xy ∈ {a, b} ∗: | x |= | y |, либо x начинается с a, а y заканчивается ab, либо ни x, ни y не являются строкой всех a}.

L2 = {xy ∈ {a, b} ∗: | x|= | y |, а x содержит подстроку aa, а y начинается с ab}.

Для обоих языков в предположении, что длина накачки равна n, я предоставил строку s = (a ^ n) (b ^ n), поскольку онаудовлетворяет условию "| x | = | y |, x начинается с a a, а y заканчивается условием ab" в L1 и "| x | = | y |, x содержит подстроку aa, а y начинается с условия ab" в L2.Итак, s = x (y ^ i) z, я выбрал x = (a ^ n-1), y = a, z = b ^ n.Для любого четного i общее количество букв нечетно в x (y ^ i) z, так что s не находится в L1 и L2, потому что | x |не может быть равным | y |больше.Мне просто интересно, правильно ли я это делаю или я что-то упускаю?

Answer 1

Для L1 пусть w = a ^ pbba ^ p.Тогда w находится в L1, потому что его можно разбить на подстроки x = a ^ pb и y = ba ^ p одинаковой длины, ни одна из которых не является строкой только a.По лемме прокачки для регулярных языков w = uvx где | uv |<= p, | v |> 0 и uv ^ kx находится в L1 для всех натуральных чисел k> = 0. Однако uv должна быть строкой a из начала строки;подкачка приведет к тому, что первая половина полученной строки x будет состоять только из a (при условии, что строка остается строкой четной длины; в противном случае строка не может быть в L1 в любом случае);откачка приведет к тому, что вторая половина полученной строки у будет состоять только из a.В любом случае, полученная строка не на языке.Это означает, что L1 не может быть регулярным.

Для L2 пусть w = a ^ paba ^ p.Подкачка означает, что результирующая строка будет начинаться с (или иметь нечетную длину), как и откачка.В первом случае результирующая строка y будет начинаться с a из первой половины w;в последнем случае результирующая строка y будет начинаться со второй половины w.В любом случае мы получаем строку не на языке, поэтому L2 также не является регулярным.