Expressões regulares sem alternância

9

Eu queria saber sobre quais conjuntos de idiomas são gerados por restrições de expressões regulares. Supondo que todas as restrições tenham um símbolo constante para cada elemento de e concatenação. Então, oito classes podem ser formadas pela presença ou ausência de complemento / negação, alteração / união e a estrela Kleene. (Sim, expressões regulares 'normais' não têm um operador , mas é conveniente aqui.)CΣC

Expressões que permitem alternância e a estrela Kleene, com ou sem complemento (o que é uma pequena explosão exponencial entre amigos?), Geram os idiomas regulares. Expressões que permitem alternância e complemento, mas não a estrela Kleene, geram os idiomas livres de estrela. Expressões que permitem alternância, mas não complemento, ou a estrela Kleene geram as linguagens finitas.

Mas qualquer classe interessante de idiomas pode ser gerada sem alternância? Sem nenhum dos três operadores, tudo o que pode ser gerado é uma única palavra. O operador de complemento não ajuda muito aqui.

Com apenas a estrela Kleene, a classe é um tanto interessante ... não está claro se eles podem ser reconhecidos mais rapidamente do que os idiomas comuns. (Existe algo não trivial sobre isso?)

Com a estrela e o complemento Kleene ... você obtém algo interessante? Essa classe tem um nome?

Esta pergunta foi inspirada na pergunta Expressão Regular em math.se.

fl.formal-languages regular-expressions Charles
fonte
o que significa alternação? Além disso, é "Kleene".
Suresh Venkat
11
@Suresh Venkat: União, OR lógico, |, /, ∪.
Charles
Observe que, no contexto original, a classe não possui complemento, mas possui referências anteriores.
Peter Taylor
@ Peter Taylor: Correto. Pretendo fazer uma pergunta de acompanhamento sobre referências anteriores, mas achei que seria demais se encaixar nessa questão.
Charles

Respostas:

12

A classe de linguagens regulares que podem ser descritas por expressões regulares sem união (e sem complementação) são conhecidos como regular, livre de união : (também star-dot regular de idiomas). Aparentemente, essa classe de idiomas recebeu atenção recentemente:

Benedek Nagy: "Linguagens regulares livres de união e autômatos de caminho livre com 1 ciclo", Publicationes Mathematicae 68 (1-2), 2006.

Sergey Afonin e Denis Golomazov: "Decomposições mínimas livres de união de linguagens regulares", Teoria e aplicações de idiomas e autômatos, Springer 2009.

Galina Jirásková e Tomás Masopust: "Complexidade em línguas regulares livres de união", Desenvolvimentos em teoria de idiomas, Springer 2010.

Hermann Gruber
fonte
11
Agradável. Sabe-se algo sobre o poder adicional da complementação?
Charles
11
Correção nitpicky curta: O artigo de Afonin e Golomazov apareceu na LATA 2009, não DLT 2009.
Dominik D. Freydenberger