Использование леммы Огдена против регулярной леммы накачки для контекстно-свободных грамматик
Поэтому я изучаю разницу между лемматами в вопросе. Каждая ссылка, которую я могу найти, использует пример:
{(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 нет а. Тогда просто качайте все, что хотите.)
Мой вопрос: как лемма Огдена меняет эту стратегию? Что делает "маркировка"?
Благодарю.
2 ответа
Один важный камень преткновения здесь заключается в том, что "возможность прокачивать" не подразумевает отсутствие контекста, а "неумение прокачивать" показывает, что оно не является контекстно-свободным. Точно так же, быть серым не значит, что ты слон, но быть слоном означает, что ты серый...
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
не является контекстно-свободным, но это не может быть продемонстрировано с помощью леммы прокачки (но может быть по лемме Огдена), и поэтому мы можем сказать, что:
Лемма Огдена - вторая, более сильная накачка леммы для языков без контекста.
Я не слишком уверен в том, как использовать здесь лемму Огдена, но ваше "доказательство" неверно. Используя лемму прокачки, чтобы доказать, что язык не является контекстно-свободным, вы не можете выбрать разбиение на uvxyz. Расщепление выбрано "для вас", и вы должны показать, что лемма не выполняется ни для одного uvxyz.