Пример неконтекстно-свободного языка, который, тем не менее, МОЖЕТ быть прокачан?

15

Таким образом, в основном L удовлетворяет условиям леммы накачки для КЛЛ, но не является КЛЛ (это возможно в соответствии с определением леммы).

user2329564
источник
Это домашнее задание или вам просто любопытно?
Юваль Фильмус
Это не домашнее задание, но я ожидаю увидеть его на экзамене (просто догадка, зная моего профессора). И мне всегда любопытно :)
user2329564
2
У нас был похожий вопрос, но для обычных языков . Применяется тот же тип конструкции: возьмите специальный символ и рассмотрим $ K { $ kk 1 } { a , b } для неприятного языка K { a , b } . $$K{$kk1}{a,b}K{a,b}
Хендрик Ян

Ответы:

13

Классический пример: . Мудрый показывает в своей статье сильная накачка леммы для контекстно-свободных языков, что ни лемма накачки Бар-Гилеля, ни теорема Париха (утверждающая, что набор длин слов в неконтекстном языке является полулинейным) не могут быть использованы для доказательства что L не является контекстно-свободным. Другие приемы, такие как пересечение с обычным языком, также не помогают. (Лемма Огдена, обобщение леммы о накачке Бар-Гилеля, доказывает, что LL={aibjck:i,j,k all different}LLне является контекстно-свободным.) Он также предоставляет альтернативную лемму прокачки, которая эквивалентна контекстно-свободной (для вычислимых языков), и использует ее, чтобы доказать, что не является контекстно-свободной.L

Насосная лемма Уайза гласит, что язык зависит от контекста тогда и только тогда, когда существует (неограниченная) грамматика G, порождающая L, и целое число k, такое что всякий раз, когда G генерирует «форму предложения» s (поэтому s может включать нетерминалы) длины | с | > k , мы можем написать s = u v x y z, где x , v y непустые, | V X Y | kLGLkGss|s|>ks=uvxyzx,vy|vxy|kи существует нетерминал такой, что G генерирует u A z, а A генерирует как v A y, так и x .AGuAzAvAyx

Повторно применяя условие в лемме, Вайз может доказать, что не является контекстно-свободным, но детали несколько сложны. Он также дает еще более сложное эквивалентное условие и использует его, чтобы доказать, что язык { a n b a n m : n , m > 0 } не может быть записан как конечное пересечение контекстно-свободных языков.L{anbanm:n,m>0}

Если вы не можете получить доступ к статье Уайза (она находится за платной стеной), существует печатная версия, которая вышла в виде технического отчета Университета Индианы.


Неконтекстно-свободный язык, который удовлетворяет условию накачки леммы Огдена, дан Джонсонбо и Миллером, Converse of pumping lemmas , и приписан там Боассону и Хорвату, О языках, удовлетворяющих лемме Огдена . Язык, о котором идет речь, это Мы можем написатьL=L1L

L=n1(e+a+d+)n(e+b+d+)n(e+c+d+)n(a+b+c+d)ΣΣ(a+b+c+e)Σ(ed+d(a+b+c)+(a+b+c)e)Σ.
, соответствующие двум разным линиям. Отметим, что L 1L 2 = и что L 2 регулярно. Лемма Огдена может быть использована для доказательства того, что L 1 не является контекстно-свободной, и поэтому не является L ' , но ее нельзя использоватьнепосредственно,чтобы показать, что L ' не является контекстно-свободной.L=L1L2L1L2=L2L1LL
Юваль Фильмус
источник
Разве не нужно, чтобы по крайней мере одно производство выглядело следующим образом: A ->
termintialForm1 AparttialForm2
Что ж, более общий: не нужно ли нетерминалу B быть частью предложения, получаемого из A, такого, что B-> termintialForm1.B.sententialfrom2 является производным от G. В противном случае, как было бы уверенным, что слово произвольную длину можно
выкачать
Я не понимаю, почему у нас есть производство , которое соответствует накачке. Например, вы немедленно восстанавливаете лемму прокачки, поскольку S u A z u v i A y i z u v i x y i z . A+vAySuAzuviAyizuvixyiz
Юваль Фильмус
4
Звучит как хорошее дополнение к нашей ссылке .
Рафаэль
Еще одна вещь, отсутствующая там - это закрытие в разделе «Обратные сопоставления GSM », см. Planetmath.org/generalizedsequentialmachine . Возможно, я добавлю это в какой-то момент.
Юваль Фильмус
8

Еще проще: . Может всегда перкачивать s; пересечение с регулярным L ( a b + c + d + ) дает не-CFL (и это может быть доказано леммой накачки).{ambncndn:m1,n1}aL(ab+c+d+)

vonbrand
источник
1
Это будет хорошим дополнением к третьему домашнему заданию ... muahaha
Ренато Санхуэса
1
Я не думаю, что это правильно. Если язык начинается с только один , затем , если вы попытаетесь накачать а , вы должны учитывать тот факт , что 0 должно быть на языке. aaa0
MCT
Чтобы расширить комментарий MCT: рассмотрите слово ; выберите v = a , u = w = x = ε , y = b p c p d p . Тогда при я = 0 , у V I ш х я у не на языке, как это не начинается с а, так что лемма не выполняется. abpcpdpv=au=w=x=εy=bpcpdpi=0uviwxiy
Потестасити
2

Простым языком является . Пересечь с L ( a b + c + d + ), чтобы получить явно не CFL, но вы всегда можете накачать a , и подражать равной длины в море{abncndn:n1}L(aa+b+c+d+)L(ab+c+d+)a .+

vonbrand
источник
Пример Мудрого (по-видимому) также невосприимчив к этим методам, как он утверждает.
Юваль Фильмус
4
@YuvalFilmus, кажется. Но мой пример невосприимчив к профессорам, которые сомневаются в том, что вы поняли работу Вайза, или хотят получить полное доказательство того, что это не КЛЛ в двухчасовом ограничении экзамена ;-)
vonbrand