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

Это не вопрос программирования, но я не знаю ни одного хорошего места в интернете, чтобы задавать вопросы по информатике. Извините, если это слишком не по теме.

Я просматриваю некоторые старые материалы CS, и я застрял на следующем:

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

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

S - > aX / bY / e

X - > bS / aXX

Y - > aS | bYY

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

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

Где я ошибаюсь?

2 2
computer-science context-free-grammar

2 ответа:

Конечно, Струну можно накачать. Пусть 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 имеет равное количество as и bs.

3

Пусть 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 находится в языке, поэтому выполняются условия леммы накачки CFL.

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

Edit: sepp2k правильно указывает, что мой выбор vxy нарушает условие, что |vxy|

1