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)p′w∈L|w|>pw=uvxyz|vxy|≤p|vy|≥1∀n≥0,uvnxynz∈L
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 ≤ pw∈L|w|>pπwA|π|0≤i<|π|siiN>0Nπi,j,k0≤i<j<k≤p
- si=sk,sj=si+N
- para todos tais que ,i ≤ n ≤ j s i ≤ s n ≤ s jni≤n≤jsi≤sn≤sj
- para todos os tais que , .j ≤ n ≤ k s k ≤ s n ≤ s knj≤n≤ksk≤sn≤sk
(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<p′lp+1πl≥p′, 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<p′AAlll|Γ|+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ˆwiji ≤ j w = u v x y z y z = ε u = wπiˆ≤jˆw=uvxyzyz=ϵ v= w i ⋯ j x= w j ⋯ | w | w x ⋯ y wxy | vxy | ≤pu=w0⋯iˆv=wiˆ⋯jˆx=wjˆ⋯|w|wx⋯ywxy|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 n∀n≥0,uvnxynz=uvnx∈Lluvnxwijn
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ππ′=π0⋯iπ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 i ≤ h ≤ s j lp ( h ) = max ( { y ≤ j | s y = h } ) fp ( h ) = min ( { y ≥ j | s y = h } ) i ≤ lp ( hl≥p′i,j,kp′hsi≤h≤sj
lp(h)=max({y≤j|sy=h})
fp(h)=min({y≥j|sy=h})j ≤ fp ( h ) ≤ ki≤lp(h)≤jj≤fp(h)≤k
Dizemos que o estado completo de um tamanho de pilha é o triplo formado por:h
- o estado do autômato na posiçãolp(h)
- o símbolo da pilha mais alta na posiçãolp(h)
- 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 i ≤ g < h ≤ s j g h ^ lp ( g ) ^ lp ( h ) ^ fp ( h ) ^ fp ( g ) w π w = u v x y z u = W 0 ⋯ ^ lp (p′p′+1sisjg,hsi≤g<h≤sjghlp(ˆ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=w0⋯lp(ˆ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|≤pk≤p
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 w∀n≥0,uvnxynz∈Lvlp(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.)
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.
fonte
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:
fonte