Prova do lema de bombeamento para linguagens sem contexto usando autômatos de empilhamento

21

O lema de bombeamento para linguagens regulares pode ser provado considerando-se um autômato de estado finito que reconhece a linguagem estudada, escolhendo uma corda com um comprimento maior que o número de estados e aplicando o princípio do buraco de pombo. O lema de bombeamento para linguagens livres de contexto (assim como o lema de Ogden, que é um pouco mais geral), no entanto, é comprovado considerando uma gramática livre de contexto da linguagem estudada, escolhendo uma sequência suficientemente longa e observando a árvore de análise.

Dada a semelhança dos dois lemas de bombeamento, você esperaria que o sem contexto também pudesse ser provado de maneira semelhante ao normal, considerando um autômato de empilhamento que reconhece o idioma, em vez de uma gramática. No entanto, não consegui encontrar nenhuma referência a essa prova.

Daí a minha pergunta: existe uma prova do lema de bombeamento para linguagens sem contexto que envolve apenas autômatos de empilhamento e não gramáticas?

a3nm
fonte

Respostas:

16

Pensei nesse problema novamente e acho que tenho uma prova completa. É um pouco mais complicado do que eu previ. Comentários são muito bem-vindos! Atualização: enviei esta prova no arXiv, caso isso seja útil para alguém: http://arxiv.org/abs/1207.2819

Seja L uma linguagem livre de contexto sobre um alfabeto Σ . Seja A um autômato de pushdown que reconheça L , com o alfabeto de pilha Γ . Nós denotamos por |A|o número de estados de A . Sem perda de generalidade, podemos assumir que as transições de A exibem o símbolo mais alto da pilha e não pressionam nenhum símbolo na pilha ou pressionam na pilha o símbolo superior anterior e algum outro símbolo.

Definimose o comprimento do bombeamento e mostrará que todos os tais tem uma decomposição na forma , de forma que , e .p = | Um | ( | Γ | + 1 ) p w L | w | > p w = u v x y z | v x y | p | v y | 1 n 0 , u v n xp=|A|2|Γ|p=|A|(|Γ|+1)pwL|w|>pw=uvxyz|vxy|p|vy|1n0,uvnxynzL

Deixe tal que . Seja um caminho aceitável de comprimento mínimo para (representado como uma sequência de transições de ), denotamos seu comprimento por. Podemos definir, para, o tamanho da pilha na posição do caminho de aceitação. Para todo , definimos um nível acima de como um conjunto de três índices com modo que:| w | > p π w A | pi | 0 i < | pi | s i i N > 0 N π i , j , k 0 i < j < k pwL|w|>pπwA|π|0i<|π|siiN>0Nπi,j,k0i<j<kp

  1. si=sk,sj=si+N
  2. para todos tais que ,i n j s is ns jninjsisnsj
  3. para todos os tais que , .j n k s ks ns knjnksksnsk

(Para um exemplo disso, veja a figura do caso 2 abaixo, que ilustra um nível ).N

Definimos o nível de como o máximo, de modo que tenha um nívelEssa definição é motivada pela seguinte propriedade: se o tamanho da pilha ao longo de um caminho se tornar maior que seu nível , os símbolos da pilha com mais de níveis de profundidade nunca serão exibidos. Agora, distinguiremos dois casos: , caso em que sabemos que a mesma configuração para o estado do autômato e os símbolos mais altos da pilha são encontrados duas vezes nas primeiras etapas de , ouπ N π N π l l l < p « l p + 1 π l p ' v ylπNπNπlll<plp+1πlp, e deve haver uma posição de empilhamento e desempilhamento que possa ser repetida um número arbitrário de vezes, a partir da qual construímos e .vy

Caso 1. . Definimos as configurações de como os pares de um estado de e uma sequência de símbolos de pilha (onde pilhas de tamanho menor que com são representadas preenchendo-as com com um símbolo em branco especial, e é por isso que usamos ao definir ). Por definição, existem essas configurações, que é menor que . Portanto, nas primeiras etapas de , a mesma configuração é encontrada duas vezes em duas posições diferentes, digamos . Denotar por A A l l l | y- | + 1 p | Um | ( | Y | + 1 ) L p p + 1 π i < j i j w i jl<pAAlll|Γ|+1p|A|(|Γ|+1)lpp+1πi<ji^ (resp. ) a posição da última letra de lida na etapa (resp. ) de . Temos . Portanto, podemos fatorar com , , , . (Por , denotamos as letras de de inclusive para exclusivo.) Por construção, .j^wijij w = u v x y z y z = ε u = wπi^j^w=uvxyzyz=ϵ v= w ij x= w j| w | w x y wxy | vxy | pu=w0i^v=wi^j^x=wj^|w|wxywxy|vxy|p

Também temos que mostrar que , mas isso decorre de nossa observação acima: símbolos de pilha mais profundos do que nunca são exibidos, portanto não há como distinguir configurações que são iguais de acordo com nossa definição e um caminho de aceitação para é construído a partir de repetindo as etapas entre e , vezes.l u v n x w i j nn0,uvnxynz=uvnxLluvnxwijn

Por fim, também temos , porque se , então, porque temos a mesma configuração nas etapas e em , seria um caminho aceitável para , contradizendo a minimaidade de .v = ϵ i j π π = π 0 i π j | pi | w π|v|>0v=ϵijππ=π0iπj|π|wπ

(Observe que esse caso equivale a aplicar o lema de bombeamento para idiomas regulares, codificando os símbolos pilha mais altos no estado de autômato, o que é adequado porque é pequeno o suficiente para garantir que seja maior que o número de estados desse autômato O principal truque é que devemos ajustar as transições .)l | w | ϵll|w|ϵ

Caso 2. . Seja um nível . Para qualquer tamanho de pilha , , associamos o último push e o primeiro pop . Por definição, e . Aqui está uma ilustração desta construção. Para simplificar o desenho, omito a distinção entre as posições do caminho e as posições das palavras que teremos que fazer mais tarde. i , j , k p h s ih s j lp ( h ) = max ( { y j | s y = h } ) fp ( h ) = min ( { y j | s y = h } ) i lp ( hlpi,j,kphsihsj lp(h)=max({yj|sy=h}) fp(h)=min({yj|sy=h})j fp ( h ) kilp(h)jjfp(h)k

Ilustração da construção do caso 2. Para simplificar o desenho, a distinção entre as posições do caminho e as posições das palavras é omitida.

Dizemos que o estado completo de um tamanho de pilha é o triplo formado por:h

  1. o estado do autômato na posiçãolp(h)
  2. o símbolo da pilha mais alta na posiçãolp(h)
  3. o estado do autômato na posiçãofp(h)

Existem possíveis estados completos e tamanhos de pilha entre e , portanto, pelo princípio pidgeonhole, existem dois tamanhos de pilha com modo que os estados completos a e são o mesmo. Como no caso 1, definimos por , , e as posições das últimas letras de lidas nas posições correspondentes em . Nós ondep + 1 s i s j g , h s ig < h s j g h ^ lp ( g ) ^ lp ( h ) ^ fp ( h ) ^ fp ( g ) w π w = u v x y z u = W 0 ^ lp (pp+1sisjg,hsig<hsjghlp(^g)lp(^h)fp(^h)fp(^g)wπw=uvxyz v= w ^ lp ( g ) ^ lp ( h ) x= w ^ lp ( h ) ^ fp ( h ) Y= w ^ fp ( h ) ^ fp ( g )u=w0lp(^g), , , e .v=wlp(^g)lp(^h)x=wlp(^h)fp(^h)y=wfp(^h)fp(^g)z=wfp(^g)|w|

Essa fatoração garante que (porque pela nossa definição de níveis).k p|vxy|pkp

Nós também temos que mostrar que . Para fazer isso, observe que cada vez que repetimos , começamos do mesmo estado e do mesmo topo da pilha e não aparecemos abaixo da nossa posição atual na pilha (caso contrário, teríamos que pressionar novamente na posição atual, violando a máxima de ), para que possamos seguir o mesmo caminho em e pressionar a mesma sequência de símbolos na pilha. Pela máxima de e a mínima de , durante a leitura de , não aparece abaixo da nossa posição atual na pilha; portanto, o caminho seguido no autômato é o mesmo, independentemente do número de vezes que repetimosv lp ( g ) A lp ( h ) fp ( h ) x v w v v v vp ( g ) A u v n x y n z wn0,uvnxynzLvlp(g)Alp(h)fp(h)xv. Agora, se repetimos quantas vezes repetimos , desde que começamos do mesmo estado, desde que empurramos a mesma sequência de símbolos na pilha com nossas repetições de , e como não exibimos mais do que tem empilhados pelo mínimo de , podemos seguir o mesmo caminho em e exibir a mesma sequência de símbolos da pilha. Portanto, um caminho de aceitação de pode ser construído a partir do caminho de aceitação para .wvvvfp(g)Auvnxynzw

Finalmente, também temos , porque, tal como no caso 1, se e , podemos construir um caminho de aceitar mais curto para removendo e .v = ε y = ε w π lp ( g ) lp ( h ) π fp ( h ) fp ( g )|vy|>1v=ϵy=ϵwπlp(g)lp(h)πfp(h)fp(g)

Portanto, temos uma fatoração adequada em ambos os casos, e o resultado é comprovado.

(O crédito é para Marc Jeanmougin por me ajudar com essa prova.)

a3nm
fonte
7

Sim, é possível. Poderíamos usar a noção de configurações de superfície; eles foram introduzidos por Cook há muito tempo. Com isso, deve ser bem fácil obter uma versão do lema de bombeamento.

Quanto às configurações de superfície, quase todo artigo sobre o LogCFL deve conter sua definição. Aqui está um artigo recente e aqui está uma tese

Talvez alguém mais enérgico possa explicar os detalhes!

V Vinay
fonte
Obrigado por responder! Sim, é bastante natural observar a combinação do estado do autômato e do símbolo da pilha superior. Ainda estou pensando neste problema e não consigo descobrir os detalhes ... A ajuda é apreciada. :-)
a3nm
3

Para completar, uma referência a uma prova nessa direção.

A.Ehrenfeucht, HJHoogeboom, G.Rozenberg: Sistemas de pares coordenados. I: Palavras dyck e bombeamento clássico RAIRO, Inf. Théor. Appl. 20, 405-424 (1986)

Abstrato. A noção de um sistema de pares coordenados [...] corresponde muito de perto (é outra formulação) à noção de autômato push-down. Neste artigo, investigamos a [...] possibilidade de obter propriedades de bombeamento de linguagens livres de contexto através da análise de cálculos em sistemas cp. Para isso, analisamos a estrutura combinatória das palavras Dyck. As propriedades das palavras Dyck que investigamos derivam da análise combinatória de cálculos em sistemas cp. Demonstramos como essa correspondência pode ser usada para provar o lema clássico de bombeamento.

Hendrik Jan
fonte
1

Ao discutir esse problema com Géraud Sénizergues, ele me apontou este artigo de Sakarovitch que já comprova esse resultado. A prova parece remontar a este artigo de Ogden.

Referências:

  • Sakarovitch, Jacques. Sur une propriété d'itération des languages ​​algébriques déterministes. (Francês. Resumo em inglês). Matemática. Teoria de Sistemas 14 (1981), n. 3, 247-288.
  • William F. Ogden. 1969. Teoremas de intercalação para linguagens de pilha. Em Anais do primeiro simpósio anual da ACM sobre Teoria da Computação (STOC '69).
Lamine
fonte