Насосная лемма для КЛЛ

Question

Мой вопрос:

Пусть L = {x в {a, b} * | х имеет одинаковое количество а и б}

Я знаю, что это язык без контекста, потому что я могу создать для него грамматику (например, epsilon):

S -> aX | bY | e

X -> bS | aXX

Y -> aS | bYY

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

Поскольку это язык без контекста, согласно лемме о накачке для КЛЛ, любая строка, длина которой превышает длину накачки p, должна быть в состоянии перекачать. Однако, если я выберу строку s = a ^ p b ^ p a ^ p b ^ p, эта строка не может быть перекачана, поэтому язык не должен быть контекстно-свободным.

Куда я иду не так?

Answer 1

Конечно, шнур можно накачать. Пусть u = a^p b^(p-1), v = b, x = e, y = a, z=a^(p-1) b^p. Теперь uvxyz = s и для любого i u v^i x y^i z имеет равное количество как и bs.

Answer 2

Пусть u = a ^ p, v = b ^ (p-1), x = ba, y = a ^ (p-1), z = b ^ p, так что ваша строка s = uvxyz.

Тогда любая строка вида u v ^ i x y ^ i z находится на языке, поэтому условия леммы прокачки КЛЛ выполнены.

Длина накачки не "p" для вашего примера ... может быть, это то, где вы запутались?

Редактировать: sepp2k правильно указывает, что мой выбор vxy нарушает условие, что | vxy | <= p, длина накачки языка. Его решение v = b, x = e, y = a является правильным. Для этого языка будет закачиваться любая строка длиной 2 или больше - где-то должны появиться «ab» или «ba», поэтому vy = ab или vy = ba всегда будут работать. </p>