Использование леммы Огдена против регулярной леммы накачки для контекстно-свободных грамматик

Question

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

{(a^i)(b^j)(c^k)(d^l) : i = 0 or j = k = l}

чтобы показать разницу между ними. Я могу найти пример, используя обычную лемму, чтобы "опровергнуть" ее.

Выберите w = uvxyz, st |vy| > 0, |vxy| <= стр. Предположим, что w содержит одинаковое количество b, c, d.

Я выбрал:

u,v,x = ε
y = (the string of a's)
z = (the rest of the string w)

Накачка y просто прибавит к числу a, и если |b|=|c|=|d| во-первых, так будет и сейчас.

(Аналогичный аргумент, если у w нет а. Тогда просто качайте все, что хотите.)

Мой вопрос: как лемма Огдена меняет эту стратегию? Что делает "маркировка"?

Благодарю.

Answer 1

Один важный камень преткновения здесь заключается в том, что "возможность прокачивать" не подразумевает отсутствие контекста, а "неумение прокачивать" показывает, что оно не является контекстно-свободным. Точно так же, быть серым не значит, что ты слон, но быть слоном означает, что ты серый...

Grammar context free        => Pumping Lemma is definitely satisfied  
Grammar not context free    => Pumping Lemma *may* be satisfied
Pumping Lemma satisfied     => Grammar *may* be context free
Pumping Lemma not satisfied => Grammar definitely not context free
# (we can write exactly the same for Ogden's Lemma)
# Here "=>" should be read as implies

То есть, чтобы продемонстрировать, что язык не является контекстно-свободным, мы должны показать, что он не (!) Удовлетворяет одному из этих леммат. (Даже если он удовлетворяет обоим, мы не доказали, что это контекстно-свободный.)

Ниже приведен набросок доказательства того, что L = { a^i b^j c^k d^l where i = 0 or j = k = l} не является контекстно-свободным (хотя он удовлетворяет лемме прокачки, он не удовлетворяет лемме Огдена):

Насосная лемма для контекстно-свободных грамматик:

Если язык L не зависит от контекста, тогда существует некоторое целое число p ≥ 1 такой, что любая строка s в L с |s| ≥ p (где p длина накачки) можно записать как s = uvxyz
с подстрокой u, v, x, y and z такой, что:
1. |vxy| ≤ p,
2. |vy| ≥ 1, а также
3. u v^n x y^n z в L за каждое натуральное число n,

В нашем примере:

Для любого s в L (с |s|>=p):

• Если s содержит a затем выберите v=a, x=epsilon, y=epsilon (и у нас нет никакого противоречия с языком, не зависящим от контекста).
• Если s не содержит a с (w=b^j c^k d^l и один из j, k или же l ненулевой, так как |s|>=1) тогда выбирай v=b (если j>0, v=c Элиф k>0 иначе v=c), x=epsilon, y=epsilon (и у нас нет противоречия с языком, не зависящим от контекста).

(Так что, к сожалению: используя лемму прокачки, мы ничего не можем доказать L !
Примечание: вышеупомянутое было по существу аргументом, который вы дали в вопросе.)

Лемма Огдена:

Если язык L не зависит от контекста, то существует некоторое число p > 0 (где p может или не может быть длина накачки), так что для любой строки w длиной не менее p в L и каждый способ "маркировки" p или более позиций в w, w можно записать как w = uxyzv
со строками u, x, y, z, а также v такой что:
1. xz имеет по крайней мере одну отмеченную позицию,
2. xyz имеет максимум p отмеченные позиции, и
3. u x^n y z^n v в L для каждого n ≥ 0,

Примечание: эта маркировка является ключевой частью леммы Огдена, она гласит: "не только каждый элемент может быть" прокачан ", но он может быть прокачан с использованием любого p отмеченные позиции ".

В нашем примере:

Позволять w = a b^p c^p d^p и отметьте позиции b с (из которых есть p, так w удовлетворяет требованиям леммы Огдена), и пусть u,x,y,z,v быть разложением, удовлетворяющим условиям леммы Огдена (z=uxyzv).

• Если x или же z содержат несколько символов, то u x^2 y z^2 w не в L потому что там будут символы в неправильном порядке (рассмотрим (bc)^2 = bcbc).
• Или x или же z должен содержать b (по условию леммы 1.)

Это оставляет нам пять случаев для проверки (для i,j>0):

• x=epsilon, z=b^i
• x=a, z=b^i
• x=b^i, z=c^j
• x=b^i, z=d^j
• x=b^i, z=epsilon

в каждом случае (сравнивая количество b s, c с и d s) мы можем видеть, что u x^2 v y^2 z не в L (и у нас есть противоречие (!) с языком, не зависящим от контекста, то есть мы доказали, что L не является контекстно-свободным).

,

Чтобы подвести итог, L не является контекстно-свободным, но это не может быть продемонстрировано с помощью леммы прокачки (но может быть по лемме Огдена), и поэтому мы можем сказать, что:

Лемма Огдена - вторая, более сильная накачка леммы для языков без контекста.

Answer 2

Я не слишком уверен в том, как использовать здесь лемму Огдена, но ваше "доказательство" неверно. Используя лемму прокачки, чтобы доказать, что язык не является контекстно-свободным, вы не можете выбрать разбиение на uvxyz. Расщепление выбрано "для вас", и вы должны показать, что лемма не выполняется ни для одного uvxyz.