Os conjuntos Antes e Depois das gramáticas sem contexto são sempre sem contexto?

14

Seja uma gramática livre de contexto. Uma série de terminais e não terminais de é dito ser uma forma sentencial de se você pode obtê-lo através da aplicação de produções de zero ou mais vezes para o símbolo de início de . Vamos ser o conjunto de formas de sentenciais .GG G S SF ( G ) GGGGSSF(G)G

Seja e seja uma subcadeia de - chamamos um fragmento de . Agora deixeαSF(G)βαSF ( G )βSF(G)

Antes(β)={γ | δ.γβδSF(G)}

e

Depois de(β)={δ | γ.γβδSF(G)} .

Os idiomas e são livres de contexto? E se for inequívoco? Se for inequívoco, e também podem ser descritos por uma linguagem livre de contexto inequívoca?Depois ( β ) G G Antes ( β ) Depois ( β )Antes(β)Depois de(β)GGAntes(β)Depois de(β)

Este é um seguimento da minha pergunta anterior , após uma tentativa anterior de facilitar a resposta da minha pergunta. Uma resposta negativa tornará difícil a pergunta abrangente sobre a qual estou trabalhando.

Alex ten Brink
fonte

Respostas:

8

Vamos ter uma ideia do e Depois ( β ) primeiro. Considere uma árvore de derivação que contém β ; "contém" aqui significa que você pode cortar subárvores para que β seja uma subpalavra da frente da árvore. Então, o conjunto anterior (depois) são todas as frentes potenciais da parte da árvore à esquerda (direita) de β :Antes(β)After(β)βββ

árvore com conjuntos antes e depois
[ fonte ]

Portanto, temos que construir uma gramática para a parte alinhada horizontalmente (alinhada verticalmente) da árvore. Isso parece fácil, pois já temos uma gramática para toda a árvore; só precisamos garantir que todas as formas sentenciais sejam palavras (alterar os alfabetos), filtrar as que não contêm (que é uma propriedade regular, pois β é fixo) e cortar tudo depois de (antes) β , incluindo β . Este corte também deve ser possível.ββββ


Agora para uma prova formal. Vamos transformar a gramática como propriedades descritas e de fecho uso de para fazer a filtragem e de corte, ou seja, nós realizar uma prova não-construtiva.CFeu

Seja uma gramática livre de contexto. É fácil ver que SF ( G ) é livre de contexto; construa G = ( N , T , δ , N S ) assim:G=(N,T,δ,S)SF(G)G=(N,T,δ,NS)

  • N={NUMAUMAN}
  • T=NT
  • δ={α(UMA)α(β)UMAβδ}{NUMAUMAUMAN}

com para todos t T e α ( A ) = N A para todos uma N . É claro que L ( G ) = SF ( G ) ; portanto, o fechamento do prefixo correspondente Pref ( SF ( G ) ) e o sufixo Suff ( SF ( G ) ) também são livres de contexto¹.α(t)=ttTα(UMA)=NUMAumaNeu(G)=SF(G)Pref(SF(G))Suff(SF(G))

Agora, para qualquer são L ( β ( N T ) * ) e L ( ( N T ) * β ) linguagens regulares. Como C F G é fechada sob cruzamento e direita / esquerda quociente com linguagens regulares, obtemosβ(NT)eu(β(NT))eu((NT)β)CFeu

Antes(β)=(Pref(SF(G))  eu((NT)β))/βCFeu

e

.Depois de(β)=(Suff(SF(G))  eu(β(NT)))βCFeu


¹ é fechado sob o quociente direito (e esquerdo) ; Pref ( L ) = G / Σ * e semelhante para Suff resp rendimento prefixo. fechamento de sufixo.CFeuPref(eu)=eu/ΣSuff

Rafael
fonte
Comecei a escrever uma resposta e percebi que minha prova era a mesma que a sua. Eu teria que colocar desta forma (comprimido para caber aqui): formar uma gramática pela adição de um novo terminal de A (a metavariable) para cada não-terminal A e uma produção A A . Então, formas sentenciais de G são as palavras reconhecidas por G que consistem em metavariáveis. Esta é a interseção de um CFG com um idioma regular e, portanto, é regular. O conjunto de prefixos de um CFG é um CFG (pegue um PDA e torne todos os estados finais). B e f o r e ( γ ) =GUMA^UMAUMAUMA^GG é de novo uma GLC. Before(γ)={γγβL(Prefix(G^))}
Gilles 'SO- stop being evil'
1
@Gilles, três comentários sobre isso: 1) os formulários sentenciais normalmente (adequadamente) contêm o idioma. 2) "tornar todos os estados finais" - isso não funcionará; você também aceitará prefixos de não-palavras. 3) O último passo para "cortar" um sufixo parece difícil de ser rigoroso. : / Você tem uma prova rigorosa mas mais compacta que a minha?
Raphael
1) não importa (mude para ter ou não um terminal para cada terminal). 2) Opa, eu cortei demais: torne todos os estados que podem chegar a um estado final final. 3) Faça um terminal b por vez; no PDA, marque os estados dos quais se pode alcançar um estado final consumindo b como final. Sim, seria preciso mais expansão para tornar isso rigoroso. Gbb
Gilles 'SO- stop being evil'
9

Sim, e Depois ( β ) são linguagens livres de contexto. Aqui está como eu provaria isso. Primeiro, um lema (que é o ponto crucial). Se L é CF, então:Before(β)After(β)L

Antes(eu,β)={γ | δ.γβδeu}

e

Depois de(eu,β)={γ | δ.δβγeu}

são CF.

Prova? Para construa um transdutor de estado finito não determinístico T β que varre uma string, emitindo todos os símbolos de entrada que vê e simultaneamente procura não deterministicamente β . Sempre que T β vê o primeiro símbolo de β , bifurca-se de forma não determinística e cessa de emitir símbolos até terminar de ver β ou vê um símbolo que se desvia de β , parando em ambos os casos. Se T ββAntes(eu,β)TββTββββTββna íntegra, aceita ao parar, que é a única maneira que aceita. Se vir um desvio de , rejeitará.β

O lema pode ser acionado para lidar com casos em que pode se sobrepor (como a b a b - continue procurando por β, mesmo durante a verificação de β anterior ) ou apareça várias vezes (na verdade, o original não determinístico) bifurcação já lida com isso). βumabumabββ

É bastante claro que , e como as CFLs são fechadas sob transdução em estado finito, Antes ( L , β ) é, portanto, CF. Tβ(eu)=Antes(eu,β)Antes(eu,β)

Um argumento semelhante vale para , ou pode ser feito com reversões de string de Before ( L , β ) , CFLs também sendo fechadas sob reversão:Depois de(eu,β)Antes(eu,β)

Depois de(eu,β)=rev(Antes(rev(eu),rev(β)))

Na verdade, agora que vejo o argumento de reversão, seria ainda mais fácil começar com , já que o transdutor para isso é mais simples de descrever e verificar - ele gera a string vazia enquanto procura por um β . Quando encontra β , bifurca-se de forma não determinística, uma bifurcação continua a procurar cópias adicionais de β , a outra bifurcação copia todos os caracteres subseqüentes literalmente da entrada para a saída, aceitando o tempo todo.Depois de(eu,β)βββ

O que resta é fazer isso funcionar tanto para formulários sentenciais quanto para CFLs. Mas isso é bem direto, uma vez que a linguagem das formas sentenciais de um CFG é ela própria uma CFL. Você pode mostrar isso substituindo todos os não terminais em todo G , digamos X , declarando X como um terminal e adicionando todas as produções X X à gramática.XGXXXX

Vou ter que pensar na sua pergunta sobre a ambiguidade.

David Lewis
fonte