Expresiones regulares con referencias al alfabeto unario

18

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ácter a(el único carácter del alfabeto)
  • X* coincide con 0 o más ocurrencias de X
  • X|Ypartidos XoY
  • 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*.

Jukka Suomela
fuente
1
¿Ha explorado los enfoques de conteo, es decir, inspeccionando la secuencia de? ¿Supongo que estás familiarizado con el trabajo de Freydenberger? El |LnorteEl |
Raphael

Respuestas:

4

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.

Holger Petersen
fuente
Bienvenido al sitio! He agregado una cita más completa a su papel.
David Richerby