Накачка леммы с языками без контекста

Question

У меня есть язык {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, который есть на языке.

Есть предложения?

Answer 1

Я бы начал с выбора немного лучшего z = a ^ (m + 2) b ^ (m + 1) c ^ (m), где m - длина накачки.Эта строка явно на языке и ее длина больше или равна m.Таким образом, предполагая, что язык является КЛЛ, к нему применима лемма прокачки.Теперь, так как вы знаете, что | vwx |<= m и это | vx |> 0, вы также знаете, что vwx должен состоять из (1) только а, (2) некоторых а и некоторых б, (3) только б, (4) некоторых б и некоторых с, или (5) только с.

Рассматривайте каждый случай индивидуально.Я сделаю первые два случая для вас.

Случай 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 является ^ (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) b ^ (m + 1 + s) c ^ (m + t).Если 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).Так как s положительно, условие, что число b должно быть строго больше, чем число c, нарушается.Таким образом, z 'не на языке, и этот случай не прокачивает.

Поскольку все пять случаев не прокачивают, лемма Pumping говорит нам, что этот язык не является контекстно-свободным.

Answer 2

Примечание : После небольшого переворота в комментариях я вижу, что я не прав и ответ Уильяма на самом деле правильный. Я оставлю этот ответ здесь, чтобы я мог указать, где моя линия рассуждений потерпела неудачу.

Я бы подумала об этом так:

Какими свойствами должны обладать подстроки v, w, x, чтобы даже иметь шанс остаться в пределах определения языка после прокачки? Ни v, ни x не могут содержать подстроки как "ab" или "bc", или они сразу же выкачивают из языка ввода. Так каждое из v и x должно быть пустым, все a, все b или все c.

Рассмотрим строку aaabbc на языке.

Теперь, что произойдет, если мы выберем u = "aa", v = "a", w = epsilon, x = "b", y = "bc"; а также насос V и х? ( Вот моя ошибка: Я не рассматривал случай n = 0, где v и x фактически удаляется из строки; независимо от того, как вы выбираете uvwxy, доказательство будет ошибка для случая n = 0 или n> 1, когда uvwxy перекачивается в uv ⁿ wx ⁿ y).

Примечание : лемму прокачки CFL можно использовать для доказательства того, что язык не является контекстно-зависимым, но подчинение насосной лемме само по себе не достаточно, чтобы показать, что язык является контекстно-свободным. Есть языки, которые не являются CF, но все условия лемма прокачки КЛЛ все еще держится. В таких случаях вы можете взглянуть на лемму Огдена , несколько более мощный тест, и посмотрите, можно ли его использовать, чтобы показать, что ваш язык не CF.

Answer 3

Лемма прокачки говорит, что если язык не зависит от контекста, то он «прокачивает».То есть, если он не содержит контекста, то:

Существует некоторая минимальная длина p, так что любая строка s длиной p или более может быть переписана s = uvxyz, где члены u и y могут повторяться вставьте любое количество раз (включая ноль).

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

Но обратная лемма прокачки неверна: существуют языки, которые прокачивают, но не являются контекстно-свободными.На самом деле, ваш язык просто такой зверь.Другими словами, ваш язык не является контекстно-свободным, но он действительно работает.(Самый простой способ доказать это - разделить s так, чтобы v = "a" и y = "b".) Поэтому лемма прокачки вряд ли будет вам полезна при анализе этого языка.Вместо этого вы можете рассмотреть лемму Огдена 1008 *.