Existe uma extensão de expressões regulares que captura as linguagens livres de contexto?

25

Em muitos trabalhos que envolvem gramáticas livres de contexto (CFGs), os exemplos de tais gramáticas apresentadas frequentemente admitem caracterizações fáceis da linguagem que geram. Por exemplo:

SumaumaSb
S

gera ,{uma2EubEu|Eu0 0}

SumaSb
SumaumaSb
S

gera e{umaEubjEuj0 0}

SumaSuma
SbSb
S

gera ou equivalentemente (onde se refere à parte capturada por ).{ ( ( uma | b ) * ) 1 ( ( uma | b ) * ) 2 | p 1 = p R 2 } p 1 ( . . . ) 1{WWRW(uma|b)}{((uma|b))1((uma|b))2p1=p2R}p1(...)1

Os exemplos acima podem ser gerados adicionando índices ( ), restrições simples sobre esses índices ( ) e correspondência de padrões com expressões regulares. Isso me faz pensar se todas as linguagens sem contexto podem ser geradas por alguma extensão das expressões regulares. i > jumaEuEu>j

Existe uma extensão de expressões regulares que podem gerar todo ou algum subconjunto significativo das linguagens livres de contexto?

Alex ten Brink
fonte
3
Observe que adicionar índices e restrições é muito poderoso: você poderá definir , que não é uma CFL. umanbncn
Shaull 17/03/2013

Respostas:

34

Sim existe. Defina uma expressão sem contexto para ser um termo gerado pela seguinte gramática:

g:: =ϵString vazia|cPersonagem c no alfabeto Σ|ggConcatenação|Padrão com falha|ggDisjunção|μα.gExpressão gramatical recursiva|αExpressão variável

Esses são todos os construtores de linguagens regulares, exceto Kleene star, que é substituída por um operador de ponto fixo geral e um mecanismo de referência variável. (A estrela Kleene não é necessária, pois pode ser definida como .)g μ α .μα.ggμα.ϵgα

A interpretação de uma expressão livre de contexto requer a contabilização da interpretação de variáveis ​​livres. Portanto, defina um ambiente para ser um mapa de variáveis ​​para idiomas (ou seja, subconjuntos de ) e deixe ser a função que se comporta como em todas as entradas, exceto e que retorna o idioma para .Σ [ ρ | α : L ] ρ α L αρΣ[ρ|α:eu]ραeuα

Agora, defina a interpretação de uma expressão livre de contexto da seguinte maneira:

[[ϵ]]ρ={ϵ}[[c]]ρ={c}[[g1g2]]ρ={W1W2|W1[[g1]]ρW2[[g2]]ρ}[[]]ρ=[[g1g2]]ρ=[[g1]]ρ[[g2]]ρ[[α]]ρ=ρ(α)[[μα.g]]ρ=nNeunOndeeu0 0=eun+1=eun[[g]][ρ|α:eun]

Usando o teorema de Knaster-Tarski, é fácil ver que a interpretação de é a menos fixa da expressão.μα.g

É simples (embora não totalmente trivial) mostrar que você pode dar uma expressão livre de contexto derivando o mesmo idioma que qualquer gramática livre de contexto e vice-versa. A não trivialidade surge do fato de que expressões sem contexto têm pontos fixos aninhados, e gramáticas sem contexto fornecem um único ponto fixo sobre uma tupla. Isso requer o uso do lema de Bekic, que diz precisamente que um ponto fixo aninhado pode ser convertido em um único ponto fixo sobre um produto (e vice-versa). Mas essa é a única sutileza.

Edição: Não, eu não sei uma referência padrão para isso: eu trabalhei para o meu próprio interesse. No entanto, é uma construção bastante óbvia que estou confiante de que foi inventada antes. Algum Googling casual revela Joost Winter, Marcello Bonsangue e o artigo recente de Jan Rutten, Linguagens sem Contexto, Coalgebraically , onde eles fornecem uma variante dessa definição (exigindo que todos os pontos fixos sejam protegidos) que eles também chamam de expressões sem contexto.

Neel Krishnaswami
fonte
Isso é incrível. Existe um nome ou referência padrão para isso?
precisa
5
Arto Salomaa aborda isso em seu livro "Línguas formais" em 1973. Ele as chama de "Expressões regulares".
Tim Schaeffer
3

Havia uma pergunta intimamente relacionada (e várias respostas) no MathOverflow sobre os idiomas cujas funções geradoras são holonômicas .

Curiosamente, a definição de Neel da semântica de acima corresponde exatamente à prova (construtiva) da existência de soluções de espécies para equações de espécies recursivas por meio do teorema implícito de espécies. Infelizmente, seu esboço de prova também deve conter um erro sutil, pois há casos em que as coisas ficam "infinitas". Em outras palavras, existe uma condição no jacobiano da transformação definida pela gramática como não singular, necessária. É provavelmente por isso que Bonsangue-Rutten exige que os pontos fixos sejam guardados, como uma maneira de garantir essa condição no jacobiano.μ

Jacques Carette
fonte
AFAICT, Winter et al. Requerem apenas proteção para garantir que você possa tomar a derivada de Brzozowski de tomando a derivada de . [ μ α .μα.g[μα.g/α]g
Neel Krishnaswami 31/03
1

Publicamos recentemente os contornos de uma estrutura que fará exatamente isso. Procure em comp.compilers , onde enviei uma notificação junto com alguns links.

Os novos desenvolvimentos funcionam com o Teorema de Chomsky-Schuetzenberger e podem ser considerados como uma conclusão desse resultado. O próprio Chomsky foi informado dos desenvolvimentos e indica um desejo de "recuperar o atraso".

Junto com esse desenvolvimento, também estabelecemos a equivalência de duas formulações separadas para expressões livres de contexto - uma que é uma extensão / conclusão da forma mu-calculus de "ponto menos fixo" (originalmente por Gruska, Yntema e McWhirter) - que recebeu uma espécie de formulação final em 2014 - e a outra publicada em 2008.

NinjaDarth
fonte
4
Inclua todas as informações relevantes na própria resposta. "Procurar sob comp.compilers" já é uma resposta inútil agora, e será completamente inútil em alguns meses.
Emil Jeřábek apoia Monica
Isso está totalmente errado. Comp.compilers (ao contrário deste site e de outros blogs, por sinal) é permanentemente arquivado. Lá você encontrará todos os detalhes necessários. Existem muitos links que podem ser encontrados lá, também no artigo publicado mais recentemente. Além disso, diferentemente dos sites de blogs, é aberto ao exterior e útil para um público muito mais amplo. Você não deve ter dificuldade em encontrar nada na USENET - que é onde perguntas como essa devem ser abordadas e discutidas. Se você tiver dificuldades, aqui está o link. groups.google.com/forum/#!topic/comp.compilers/YCa5jHUR1iQ
NinjaDarth 16/11/18
2
A questão não é que não esteja arquivado, mas que os arquivos são vastos. Quando olho os arquivos agora , encontro sua postagem em algum lugar próximo ao topo, mas quando alguém vir essa resposta em alguns meses ou anos no futuro, eles não terão idéia de por onde começar a cavar. É arrogante e rude fazer com que os leitores façam uma pesquisa longa e não confiável quando você pode apontá-los para um local mais específico. Agora, eu fiz isso por você. Demorou 30 segundos. Você poderia ter feito isso sozinho.
Emil Jeřábek apoia Monica