L = {a^n b c^n | i больше 1 и меньше 100, n больше 1}Почему следующий язык удовлетворяет лемме о перекачке для cfl
Я думаю, что неправильно понял лемму о перекачке для cfl. Почему не могу выбрать слово z = a^ncb^n, а затем разбить его на u = a^sv = a^ns w = epsilon x = b, y = b^n, затем прокачать его с i = 0, затем получить противоречие, так как 0 b не удовлетворяет языку? Я, вероятно, что-то здесь не вижу.
Какую формулировку леммы о перекачке вы используете? Заявление Сиппера об этом в «Введение в теорию вычислений» требует, чтобы все строки _s_ в _L_ по крайней мере до тех пор, пока длина накачки может быть разделена на * пять * штук, _s = uvxyz_. Кажется, вы раскалываетесь на четыре части. (NB: Ваш _z_ является Sipser's _s_, и вам не хватает его _z_.) –
Что такое i в определении языка? В вашей факторизации c не появляется. Вероятно, вы имеете в виду x = c. –