Таким образом, в основном L удовлетворяет условиям леммы накачки для КЛЛ, но не является КЛЛ (это возможно в соответствии с определением леммы).
formal-languages
context-free
pumping-lemma
user2329564
источник
источник
Ответы:
Классический пример: . Мудрый показывает в своей статье сильная накачка леммы для контекстно-свободных языков, что ни лемма накачки Бар-Гилеля, ни теорема Париха (утверждающая, что набор длин слов в неконтекстном языке является полулинейным) не могут быть использованы для доказательства что L не является контекстно-свободным. Другие приемы, такие как пересечение с обычным языком, также не помогают. (Лемма Огдена, обобщение леммы о накачке Бар-Гилеля, доказывает, что LL={aibjck:i,j,k all different} L L не является контекстно-свободным.) Он также предоставляет альтернативную лемму прокачки, которая эквивалентна контекстно-свободной (для вычислимых языков), и использует ее, чтобы доказать, что не является контекстно-свободной.L
Насосная лемма Уайза гласит, что язык зависит от контекста тогда и только тогда, когда существует (неограниченная) грамматика G, порождающая L, и целое число k, такое что всякий раз, когда G генерирует «форму предложения» s (поэтому s может включать нетерминалы) длины | с | > k , мы можем написать s = u v x y z, где x , v y непустые, | V X Y | ≤ kL G L k G s s |s|>k s=uvxyz x,vy |vxy|≤k и существует нетерминал такой, что G генерирует u A z, а A генерирует как v A y, так и x .A G uAz A vAy x
Повторно применяя условие в лемме, Вайз может доказать, что не является контекстно-свободным, но детали несколько сложны. Он также дает еще более сложное эквивалентное условие и использует его, чтобы доказать, что язык { a n b a n m : n , m > 0 } не может быть записан как конечное пересечение контекстно-свободных языков.L {anbanm:n,m>0}
Если вы не можете получить доступ к статье Уайза (она находится за платной стеной), существует печатная версия, которая вышла в виде технического отчета Университета Индианы.
Неконтекстно-свободный язык, который удовлетворяет условию накачки леммы Огдена, дан Джонсонбо и Миллером, Converse of pumping lemmas , и приписан там Боассону и Хорвату, О языках, удовлетворяющих лемме Огдена . Язык, о котором идет речь, это Мы можем написатьL′=L1∪L
источник
Еще проще: . Может всегда перкачивать s; пересечение с регулярным L ( a b + c + d + ) дает не-CFL (и это может быть доказано леммой накачки).{ambncndn:m≥1,n≥1} a L(ab+c+d+)
источник
Простым языком является . Пересечь с L ( a b + c + d + ), чтобы получить явно не CFL, но вы всегда можете накачать a , и подражать равной длины в море{abncndn:n≥1}∪L(aa+b+c+d+) L(ab+c+d+) a .+
источник