Ajuste:
- expresiones regulares con referencias
- lenguaje unario (alfabeto de 1 símbolo)
¿Se puede resolver el siguiente problema en esta configuración:
- Dada una expresión regular con referencias inversas, ¿define un lenguaje regular?
Por ejemplo, (aa+)\1define un lenguaje regular, mientras (aa+)\1+que no. ¿Podemos decidir cuál es el caso?
Para concreción, "expresiones regulares con referencias inversas" se refieren, por ejemplo, al siguiente subconjunto de las expresiones regulares habituales compatibles con Perl :
acoincide con el caráctera(el único carácter del alfabeto)X*coincide con 0 o más ocurrencias deXX|YpartidosXoY- los paréntesis se pueden usar para agrupar y capturar
\1.\2, etc. coinciden con la misma cadena que el primer, segundo, etc. par de paréntesis
También podemos usar las manos cortas normales, por ejemplo, X+= XX*.
formal-languages
computability
regular-languages
undecidability
regular-expressions
Jukka Suomela
fuente
fuente
Respuestas:
La construcción en la prueba del Teorema 9 en mi artículo Sobre Expresiones Prácticas Regulares proporciona evidencia contra la decidibilidad efectiva del problema : Podrías determinar si hay muchos primos de Fermat.
fuente