Почему следующий язык удовлетворяет лемме о накачке для cfl

L = {а ^ п б с ^ п | i больше 1 и меньше 100, n больше 1}

Я думаю, что неправильно понял лемму о прокачке для cfl. почему я не могу выбрать слово z = a ^ ncb ^ n, а затем разбить его на u = a ^ sv = a ^ ns w = epsilon x = b, y = b ^ n, затем накачать его с помощью i = 0, а затем получить противоречие так как 0 b не удовлетворяет язык? Я, наверное, что-то здесь упускаю.


person gil    schedule 16.07.2016    source источник
comment
Какую формулировку леммы о накачке вы используете? Утверждение Сипсера об этом во «Введении в теорию вычислений» требует, чтобы все строки s в L по крайней мере до тех пор, пока длина накачки могла быть разделена на пять штук, s = uvxyz. Вы как будто распадаетесь на четыре части. (Примечание: ваш z — это s Сипсера, и вам не хватает его z.)   -  person Sage Mitchell    schedule 17.07.2016
comment
Что такое i в определении языка? В вашей факторизации c не появляется. Вероятно, вы имели в виду x=c.   -  person Peter Leupold    schedule 18.07.2016


Ответы (1)


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

Ваша факторизация действительно привела бы к выходу из языка, но есть и другие, которые этого не делают.

person Peter Leupold    schedule 18.07.2016