У меня есть язык {a^i b^j c^k | i,j,k>=0 & i>j & j>k}. Я начал с предположения, что для меня выбрано какое-то m, такое, что строка
z = a^m b^(m-1) c^(m-2)
Затем строка разделяется на (z =) uvwxy, чтобы vx не были пустыми, и #(vwx)<=m. Затем, когда я выбираю "i", я запутываюсь. Скажем, я выбираю i=1, тогда у меня есть: uv^1wx^1y, и я не совсем уверен, что делать дальше, потому что мне кажется, что я мог бы выбрать vwx, который ЕСТЬ на языке.
Какие-либо предложения?
Я бы начал с выбора немного лучшего z = a ^ (m + 2) b ^ (m + 1) c ^ (m), где m - длина накачки. Эта строка явно написана на языке, и ее длина больше или равна m. Итак, если язык является CFL, к нему применима лемма о накачке. Теперь, когда вы знаете, что | vwx | ‹= M и что | vx | > 0, вы также знаете, что vwx должен состоять из (1) только a, (2) некоторых a и некоторых b, (3) только b, (4) некоторых b и некоторых c, или (5) только c.
Разбираемся с каждым случаем индивидуально. Я сделаю за вас первые два случая.
Случай 1: это означает, что vx является ^ (s) для некоторого s> 0, поскольку лемма сообщает нам | vx | > 0. Теперь предположим, что вы выбрали i = 0. Тогда лемма говорит нам, что z '= uv ^ (0) wx ^ (0) y все еще должно принадлежать языку. Однако z 'имеет вид a ^ (m + 2-s) b ^ (m + 1) c ^ (m) и, поскольку s> 0, нарушает условие, что количество a должно быть строго больше, чем количество б. Таким образом, z 'отсутствует в языке, и этот случай не может быть прокачан.
Случай 2: это означает, что vx является a ^ (s) b ^ (t) для некоторых s, t таких, что s + t> 0. Предположим, вы снова берете i = 0. Тогда z 'имеет вид a ^ (m + 2-s) b ^ (m + 1-t) c ^ (m). Если t положительно, то условие, что количество b должно быть строго больше, чем количество c, нарушается. Если t равно нулю, s должно быть положительным, и в этом случае мы переходим к случаю 1. Таким образом, z 'отсутствует в языке, и этот случай не может быть прокачан.
Чтобы иметь дело с другими случаями, помните, что вы можете выбрать разный показатель накачки i для каждого из них.
Изменить: (из прошлого обсуждения этого вопроса я решил показать три других случая.)
Случай 3: Это означает, что vx равно b ^ (s) для некоторого s> 0. Возьмем i = 0. Тогда z 'имеет вид a ^ (m + 2) b ^ (m + 1-s) c ^ ( м). Поскольку s положительно, это нарушает условие, согласно которому количество b должно быть строго больше, чем количество c. Значит, z 'отсутствует в языке, и в данном случае не получается перекачать. (Вы также можете принять i равным любому, кроме 1, чтобы показать, что в этом случае не работает прокачка.)
Случай 4: Это означает, что vx есть b ^ (s) c ^ (t) для некоторых s, t таких, что s + t> 0. Возьмем i = 2. Тогда z 'имеет вид a ^ (m + 2) Ь ^ (т + 1 + с) с ^ (т + т). Если s не равно нулю, то условие, что количество a строго больше, чем количество b, нарушается. Если s равно нулю, то t должно быть ненулевым, и в этом случае условие, что количество b должно быть строго больше, чем количество c, нарушается. Значит, z 'нет в языке, и этот случай тоже не качает.
Случай 5: Это означает, что vx есть c ^ (s) для некоторого s> 0. Возьмем i = 2. Тогда z 'имеет вид a ^ (m + 2) b ^ (m + 1) c ^ (m + с). Поскольку s положительно, условие, что количество b должно быть строго больше, чем количество c, нарушается. Значит, z 'отсутствует в языке, и в данном случае не получается перекачать.
Поскольку все пять случаев не работают, лемма о накачке говорит нам, что этот язык не является контекстно-независимым.
Примечание. После того, как я прокомментировал, я понял, что ошибаюсь, и ответ Уильяма действительно правильный. Я оставлю этот ответ здесь, чтобы указать, где мои рассуждения потерпели неудачу.
Я бы подумал об этом так:
Какие свойства должны иметь подстроки v, w, x, чтобы даже иметь шанс остаться в пределах определения языка после перекачки? Ни v, ни x не могут содержать подстроки типа «ab» или «bc», иначе они немедленно выкачиваются из языка ввода. Таким образом, каждое из v и x должно быть либо пустым, либо все a, все b или все c.
Рассмотрим строку aaabbc в языке.
Теперь, что произойдет, если мы выберем u = "aa", v = "a", w = epsilon, x = "b", y = "bc"; и качать v и x? (Вот моя ошибка: я не рассматривал случай n = 0, где v и x фактически удалены из строки; независимо от того, как вы выберете uvwxy, доказательство не удастся либо для n = 0 или n> 1 случай, когда uvwxy перекачивается до uv n wx n y).
Примечание. Лемму о перекачке CFL можно использовать, чтобы доказать, что язык не является контекстно-независимым, но выполнение леммы о перекачке само по себе недостаточно, чтобы показать, что язык < em> не зависит от контекста. Существуют языки, которые не являются CF, но все условия леммы CFL о накачке остаются в силе. В таких случаях вам может потребоваться взглянуть на лемму Огдена, более мощную проверьте, можно ли это использовать, чтобы показать, что ваш язык не CF.
Лемма о перекачке говорит, что если язык контекстно-свободный, он «перекачивает». То есть, если он контекстно-свободный, то:
Существует некоторая минимальная длина p, так что любую строку s длины p или больше можно переписать s = uvxyz, где члены u и y могут повторяться на месте любое количество раз (включая ноль).
Типичное использование - продемонстрировать, что язык не перекачивает, чтобы доказать, что он не свободен от контекста. Судя по вашей работе, похоже, это именно то, что вы пытаетесь сделать.
Но обратное утверждение леммы о перекачке неверно: существуют языки, которые перекачивают, но не зависят от контекста. На самом деле ваш язык - просто чудовище. Другими словами, ваш язык не зависит от контекста, но он работает. (Самый простой способ доказать это - разделить s так, чтобы v = "a" и y = "b".) Следовательно, лемма о перекачке вряд ли будет полезна вам при анализе этого языка. Вместо этого вы можете рассмотреть лемму Огдена.
