Я понимаю, что эта ветка старая, но на всякий случай это может помочь другому студенту в той же ситуации, вот некоторые обсуждения. Этот язык является регулярным, и вы не можете показать его как нерегулярный, используя лемму прокачки.
Чтобы увидеть, что оно регулярное, достаточно создать регулярное выражение для его генерации или NFA для его распознавания. Регулярное выражение тривиально: (ab) *. НФА проста: два состояния; исходное состояние принятия, другого нет; переход от начального к другому на; от другого к начальному на б. Готово.
Давайте посмотрим, почему лемму прокачки нельзя использовать для этого. Чтобы использовать лемму прокачки, вам нужно выбрать подходящую подстроку для прокачки. Для этого языка, независимо от размера строки, вы всегда найдете следующую подстроку в диапазоне символов длиной не менее 2: ab. Поскольку это всегда может быть подстрока, составляющая цикл, о котором говорит лемма прокачки, нет никакого способа исключить, что у вас есть обычный язык с (ab) * где-то внутри него, используя только лемму прокачки. (Примечание: для достаточно длинных строк вы не можете исключить подстроку ba). Так как вы не можете выбрать подстроку, которая будет перекачена (есть ограничения на то, где ее можно взять, но они помещены в лемму, а не то, что вы решаете), если какая-либо из подстрок сработает, вы потеряете и перекачка лемма ничего не демонстрирует.
Показать, например, что L = {a ^ k b ^ k | k> = 0} не является регулярным с использованием леммы прокачки, вам нужно выбрать строку, для которой не имеет значения, какую подстроку вы берете, при условии, что она удовлетворяет условиям PL. Вот почему, например, взятие ^ n b ^ n работает (все подстроки, удовлетворяющие гипотезам PL, имеют форму a +, и накачка, которая изменит число a без изменения числа b).