Caracterização de

16

É uma prova padrão em cursos de autômato que para e | Σ | 2 que S ( L ) = { w w : w L } não é uma linguagem livre de contexto.L=Σ|Σ|2S(L)={ww:wL}

Também é verdade que para qualquer finito , S ( L ) é finito (e, portanto, uma CFL). Eu estou supondo que L sendo infinito e regular não é "suficiente" para S ( L ) não ser uma CFL. Edit : e quanto a L não-CFL ?LS(L)LS(L)L

Existe alguma caracterização do que tem S ( L ) não sendo uma CFL?LS(L)

Ryan
fonte
Se bem entendi, a questão é decidir, dada uma linguagem regular , se S ( L ) é livre de contexto ou não. LS(L)
J.-E.
2
1. Você pode nos dizer mais sobre que tipo de caracterização você está procurando? Você está procurando um algoritmo que, dado , decida se S ( L ) é livre de contexto? Você está procurando algumas condições em L que sejam suficientes para garantir que S ( L ) seja livre de contexto? Que forma você gostaria que uma caracterização levasse? 2. Se você não obtiver respostas após alguns dias e preferir ver isso no CSTheory.SE, sinta-se à vontade para sinalizá-lo para obter atenção do moderador e solicitar a migração. LS(L)LS(L)
DW
@DW 1. Seria bom, mas eu preferiria condições suficientes. 2. Obrigado pela dica!
Ryan
11
@ Ryan apenas condições suficientes? Bem, aqui são um par: (a) L é regular e para cada em L , w = w R (b), L é CF e para todos os n , L Σ n ou é vazio ou igual a Σ n . Definitivamente, estes não são necessários. Se você não obtiver respostas aqui, mova a pergunta para cstory. Estou realmente curioso sobre as condições necessárias e suficientes! wLw=wRnLΣnΣn
Aelguindy 30/10
infinito e regular de fato não é suficiente para S ( L ) e não CF. Se Σ = { a , b , c } , L = a ∗, então S ( LLS(L)Σ={a,b,c},L=a que é regular, consequentemente, CF. S(L)=(aa)
chi

Respostas:

2

Mais um comentário estendido com uma conjectura, mas aqui está uma condição que parece capturar o problema, no contexto de regular para S ( L ) ser livre de contexto.LS(L)

Condição No mínimo DFA para L , qualquer caminho de aceitação contém no máximo um loop.AL

Exceção: dois loops são permitidos se seus rótulos e o rótulo do prefixo antes do primeiro loop comutarem e o sufixo após o segundo loop estiver vazio. Por exemplo, está ok.aab(aa)

Lembre-se de que duas palavras e v são comutadas se forem potências da mesma palavra t . Podemos assumir o sufixo vazio, porque ele não pode estar vazio e comutar com o rótulo do segundo loop em um DFA.uvt

Suficiente assumir a condição, você constrói um PDA para tratando cada padrão aceitar x u y de A , onde u rotula um loop simples. Queremos aceitar palavras da forma x u n y x u n y . Lemos x , pressionamos um símbolo para cada ocorrência deLxuyAuxunyxunyx , lemos y x , depois exibimos um símbolo para cada ocorrência de u e, finalmente, lemos y .uyxuy

Sobre a exceção, se estivermos neste caso, um caminho básico de aceitação é da forma que u , v são os rótulos dos loops. Aceitamos palavras da forma x u n y v m x u n y v m , mas, por suposição ( x , u , v comutar), é a mesma que u n x y u n v m x y v m , que pode ser feito por um PDA: push nxuyvu,vxunyvmxunyvmx,u,vunxyunvmxyvmnvezes (para ocorrências de ), leia x y , pop n vezes, pressione m vezes (para v ), leia x y , pop m vezes.uxynmvxym

O PDA final é a união dos PDAs para cada padrão.

Necessário (ondulação manual) Se houver um caminho com dois loops, mesmo no caso mais simples em que você deve pegar um e depois o outro (por exemplo, ), lembre-se de quantas vezes cada um é seguido, mas a estrutura da pilha impede que você os repita na mesma ordem. Observe que o fato de o DFA ser mínimo é importante na caracterização, para evitar o uso de dois loops quando um for suficiente.ab

Por enquanto, a parte necessária é apenas uma conjectura, e mais exceções podem ser necessárias para obter a condição exata. Eu estaria interessado em contra-exemplos.

Denis
fonte
"e, em seguida, lendo w novamente, exibindo um símbolo para cada loop feito na segunda ocorrência da palavra" - mas existem infinitamente muitos desses ! A menos que esteja lendo seu argumento incorretamente. w
Ryan
@ Ryan, o número de "padrões" xuy onde u rotula um loop é finito, para que possamos adivinhar qual deles estamos lendo.
Denis
Eu editei para esclarecer esta parte.
Denis
A condição se parece comigo a outra que eu tinha em mente: S (L) é livre de contexto se não existirem palavras , de modo que w 1 e w 2 não sejam o prefixo um do outro e u ( w 1 + w 2 ) * v L . u,v,w1,w2w1w2u(w1+w2)vL
Holf
@holf seu não parecem trabalhar para ab
Denis