Expresiones regulares sin alternancia.

9

Me preguntaba qué conjuntos de idiomas se generan por restricciones de expresiones regulares. Supongamos que todas las restricciones tienen un símbolo constante para cada elemento de y concatenación. Entonces se pueden formar ocho clases por la presencia o ausencia de complemento / negación, alteración / unión y la estrella de Kleene. (Sí, las expresiones regulares 'normales' no tienen un operador , pero es conveniente aquí).CΣC

Las expresiones que permiten la alternancia y la estrella de Kleene, con o sin complemento (¿qué es una pequeña explosión doble exponencial entre amigos?), Generan los idiomas regulares. Las expresiones que permiten la alternancia y el complemento, pero no la estrella de Kleene, generan los lenguajes sin estrellas. Las expresiones que permiten alternar pero no complementar o la estrella de Kleene generan los lenguajes finitos.

Pero, ¿se pueden generar clases de idiomas interesantes sin alternancia? Sin ninguno de los tres operadores, todo lo que se puede generar es una sola palabra. El operador del complemento no ayuda mucho aquí.

Con solo la estrella de Kleene, la clase es algo interesante ... no está claro si se pueden reconocer más rápido que los idiomas normales. (¿Se sabe algo no trivial sobre esto?)

Tanto con la estrella de Kleene como con el complemento ... ¿obtienes algo interesante? ¿Esta clase tiene un nombre?

Esta pregunta se inspiró en la pregunta de expresión regular en math.se.

Charles
fuente
¿Qué significa alternancia? Además, es "Kleene".
Suresh Venkat
1
@Suresh Venkat: Unión, OR lógico, |, /, ∪.
Charles
Tenga en cuenta que en el contexto original, la clase no tiene complemento, pero tiene referencias inversas.
Peter Taylor
@ Peter Taylor: Correcto. Tengo la intención de hacer una pregunta de seguimiento sobre referencias posteriores, pero pensé que sería demasiado para encajar en esta pregunta.
Charles

Respuestas:

12

La clase de los lenguajes regulares que pueden describirse mediante expresiones regulares sin la unión (y sin complementación) se conocen como regulares libres de sindicatos : (también estrella-punto regular de idiomas). Esta clase de idiomas aparentemente ha recibido alguna atención recientemente:

Benedek Nagy: "Lenguajes regulares sin unión y autómatas de ruta libre de 1 ciclo", Publicationes Mathematicae 68 (1-2), 2006.

Sergey Afonin y Denis Golomazov: "Descomposición mínima sin unión de lenguas regulares", Teoría y aplicaciones de lenguajes y autómatas, Springer 2009.

Galina Jirásková y Tomás Masopust: "Complejidad en lenguas regulares sin unión", Desarrollos en teoría del lenguaje, Springer 2010.

Hermann Gruber
fuente
1
Agradable. ¿Se sabe algo sobre el poder adicional de la complementación?
Charles
1
Corrección puntual breve: el artículo de Afonin y Golomazov apareció en LATA 2009, no en DLT 2009.
Dominik D. Freydenberger