Las expresiones regulares "densas" generan

Aquí hay una conjetura para expresiones regulares:

Para la expresión regular , deje que la longitudser el número de símbolos que contiene, ignorando paréntesis y operadores. Ej. $R$ $|R|$ $|0 \cup 1| = |(0 \cup 1)^*| = 2$

Conjetura: Si y contiene cada cadena de longitudo menos, entonces . $|R| > 1$ $L(R)$ $|R|$ $L(R) = \Sigma^*$

Es decir, si es 'densa' hasta longitud 's, entonces realmente genera todo. $L(R)$ $R$ $R$

Algunas cosas que pueden ser relevantes:

Solo se necesita una pequeña parte de para generar todas las cadenas. Por ejemplo, en binario, funcionará para cualquier . $R$ $R = (0 \cup 1)^* \cup S$ $S$
Tiene que haber una estrella de Kleene en $R$ en algún momento. Si no lo hay, perderá una cadena de tamaño menor que. $|R|$

Sería bueno ver una prueba o contraejemplo. ¿Hay algún caso en el que obviamente esté mal que me haya perdido? ¿Alguien ha visto esto (o algo similar) antes?

formal-languages regular-languages regular-expressions Lucas Cook
fuente

¿Se cuentan

como o como ?

ε

$\varepsilon$

\emptyset

$\emptyset$ symbolsoperations

Ran G.

@Ran, los estaba contando como símbolos.

Lucas Cook,

Respuestas:

Keith Ellul, Bryan Krawetz, Jeffrey Shallit y Ming-wei Wang refutan su conjetura en su artículo "Expresiones regulares: nuevos resultados y problemas abiertos". Si bien el documento no está disponible en línea, un charla .

En el documento, definen la medida , que es el número de símbolos en , sin contar o . Sin embargo, puede eliminarse de cada expresión que no genere el lenguaje vacío, y la expresión puede "limpiarse" para que el número de que contiene sea como máximo $|\mathrm{alph}(R)|$ $R$ $\epsilon$ $\emptyset$ $\emptyset$ $\epsilon$ $|\mathrm{alph}(R)|$ (Lema en la página 10 de la charla).

En la página 51, por cada construyen una expresión regular de tamaño sobre que genera todas las cadenas de tamaño como máximo , pero no genera todas las cadenas. Tenga en cuenta que "tamaño" aquí es tanto en su sentido como en el de ellos, ya que estamos usando la notación big-O. También plantean una pregunta abierta para encontrar la mejor dependencia entre los dos parámetros. $n \geq 3$ $O(n)$ $\{0,1\}$ $\Omega(2^n n)$

Yuval Filmus
fuente

Muy buen resultado, y bastante sorprendente también :)

Alex ten Brink

¿Cómo se ve esa expresión regular?

svick

@svick: combina ingeniosamente el truco que

con estrellas de Kleene para capturar subcadenas comunes, a juzgar por una rápida ojeada de la prueba. La expresión es bastante monstruosa :)

(a + b) (c + d) = a c + b c + a d + b d

$(a+b)(c+d)=ac+bc+ad+bd$

Alex ten Brink

@Yuval Muy guay. Gracias por la referencia!

Lucas Cook

@YuvalFilmus Parece que el documento está disponible en línea ahora.

Anton Trunov