É 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.
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 ?
Existe alguma caracterização do que tem S ( L ) não sendo uma CFL?
context-free
Ryan
fonte
fonte
Respostas:
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.L S(L)
Condição No mínimo DFA para L , qualquer caminho de aceitação contém no máximo um loop.A L
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.aa∗b(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.u v t
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 deL xuy A u xunyxuny x , lemos y x , depois exibimos um símbolo para cada ocorrência de u e, finalmente, lemos y .u yx u y
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 nxuyv u,v xunyvmxunyvm x,u,v unxyunvmxyvm n vezes (para ocorrências de ), leia x y , pop n vezes, pressione m vezes (para v ), leia x y , pop m vezes.u xy n m v xy m
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.a∗b∗
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.
fonte