Exemplo de uma linguagem livre de contexto que, no entanto, PODE ser bombeada?

15

Portanto, basicamente L satisfaz as condições do lema de bombeamento para CFLs, mas não é uma CFL (isso é possível de acordo com a definição do lema).

user2329564
fonte
Esta é uma pergunta de lição de casa ou você está apenas curioso?
Yuval Filmus
Este não é um dever de casa, mas espero vê-lo no exame (apenas um palpite, conhecendo meu professor). E eu sou sempre curioso :)
user2329564
2
Tivemos uma pergunta semelhante, mas para idiomas regulares . O mesmo tipo de construção se aplica: pegue um símbolo especial $ e considere $K{$kk1}{a,b} para uma linguagem desagradável K{a,b} .
Hendrik Jan

Respostas:

13

O exemplo clássico é . Wise mostra em seu artigo Um forte lema de bombeamento para linguagens sem contexto que nem o lema de Bar-Hillel nem o teorema de Parikh (afirmando que o conjunto de comprimentos de palavras em uma linguagem sem contexto é semi-linear) podem ser usados ​​para provar que L não é livre de contexto. Outros truques como cruzar com um idioma comum também não ajudam. (O lema de Ogden, uma generalização do lema de bombeamento de Bar-Hillel, prova que LL={aibjck:i,j,k all different}LLEle também fornece um lema de bombeamento alternativo equivalente à ausência de contexto (para linguagens computáveis) e o utiliza para provar que não é livre de contexto.L

O lema de bombeamento de Wise afirma que uma linguagem é livre de contexto se e somente se houver uma gramática (irrestrita) G gerando L e um número inteiro k, de modo que sempre que G gere uma "forma sentencial" s (para que s possam incluir não terminais) de comprimento | s | > k , podemos escrever s = u v x y z onde x , v y não estão vazios, | v x y | kLGLkGss|s|>ks=uvxyzx,vy|vxy|k, E não é um produto não-terminal de tal forma que L gera u Um z e A gera tanto v Um y e x .AGuAzAvAyx

Ao aplicar repetidamente a condição no lema, o Wise pode provar que não é livre de contexto, mas os detalhes são um pouco complicados. Ele também fornece uma condição equivalente ainda mais complicada e a usa para provar que a linguagem { a n b a n m : n , m > 0 } não pode ser escrita como uma interseção finita de linguagens livres de contexto.L{anbanm:n,m>0}

Se você não consegue acessar o artigo de Wise (está atrás de um paywall), há uma versão datilografada que saiu como um relatório técnico da universidade de Indiana.


Uma linguagem não isenta de contexto que satisfaça a condição de bombeamento do lema de Ogden é dada por Johnsonbaugh e Miller, Converse de lemas de bombeamento , e atribuída a Boasson e Horvath, em idiomas que satisfazem o lema de Ogden . O idioma em questão é Podemos escreverL=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)Σ.
, correspondendo às duas linhas diferentes. Observe que L 1L 2 = e que L 2 é regular. O lema de Ogden pode ser usado para provar que L 1 não é livre de contexto e, portanto, também não é L ' , mas não pode ser usadodiretamentepara mostrar que L ' não é livre de contexto.L=L1L2L1L2=L2L1LL
Yuval Filmus
fonte
Não é necessário para ser pelo menos uma produção parecido com isto: A -> sententialForm1 A sententialForm2 para qualquer bombeamento para ser possível
user2329564
Bem mais geral: não é necessário que um B não terminal faça parte de uma forma sentencial derivável de A, de modo que B-> sententialForm1.B.sententialfrom2 seja uma produção de G. Caso contrário, como seria certo que uma palavra de um comprimento arbitrário pode ser bombeado de A.
user2329564 15/13
Não vejo por que, temos uma produção , que corresponde ao bombeamento. Por exemplo, a recuperar imediatamente o bombeamento lema desde S * u Um z * u v i Um y i z * u v i x y i z . A+vAySuAzuviAyizuvixyiz
Yuval Filmus 15/05
4
Parece uma boa adição à nossa referência .
Rafael
Outra coisa que falta é o fechamento em "mapeamentos inversos de G / M ", consulte planetmath.org/generalizedsequentialmachine . Talvez eu os adicione em algum momento.
Yuval Filmus
8

Ainda mais simples: . Pode sempre bombear os a ; A interseção com o L regular ( a b + c + d + ) fornece um não-CFL (e isso pode ser provado pelo bombeamento do lema).{ambncndn:m1,n1}aL(ab+c+d+)

vonbrand
fonte
11
Esta será uma boa adição para a terceira lição de casa ... muahaha
Renato Sanhueza
11
Eu não acho que isso esteja certo. Se o idioma começar com apenas um , se você tentar bombear o a , deverá considerar o fato de que um 0 também deve estar no idioma. aaa0
MCT
Para expandir o comentário do MCT: considere a palavra ; escolha v = a , u = w = x = ε , y = b p c p d p . Então, para i = 0 , u v i w x i y não é na língua, uma vez que não começar com um a, de modo que o lema não se sustenta. abpcpdpv=au=w=x=εy=bpcpdpi=0uviwxiy
Potestity
2

A simple language is {abncndn:n1}L(aa+b+c+d+). Intersect with L(ab+c+d+) to get a clearly non-CFL, but you can always pump the a, and mimetize the equal-length-ness in the sea of +.

vonbrand
fonte
Wise's example is (apparently) immune to these techniques as well, or so he claims.
Yuval Filmus
4
@YuvalFilmus, so it seems. But my example is immune to professors doubting you understood Wise's paper, or wanting a complete proof that it isn't a CFL in the 2-hour limit of the exam ;-)
vonbrand