Expresiones regulares de familias de expresiones regulares

Estaba leyendo sobre el problema de la altura de las estrellas y noté que la familia de expresiones regulares de Eggan sigue un patrón simple que puede describirse mediante una expresión regular. Mi pregunta es: ¿hay resultados interesantes sobre expresiones regulares que describan familias de expresiones regulares? ¿Puede este proceso continuar más allá, de modo que tenga una expresión regular que describa una familia de expresiones regulares, cada una de las cuales describe una familia de expresiones regulares? Solo un pensamiento.

Los lenguajes regulares están cerrados bajo unión, concatenación y estrella, por lo que las expresiones regulares bajo expresiones regulares describen lenguajes regulares. Entonces, regex, que describe regex, que describe regex todavía describe una familia de lenguajes regulares, y puede continuar ese proceso todo el tiempo que desee.

Aquí, por «describir» quiero decir que primero, solo tiene expresiones regulares, como y regulares , que describe el nivel 1 de como , esta expresión regular describe los idiomas , , , ... y así sucesivamente. ( a | b b ) + = R 1 ( R 0 R ∗ 1 R 0 ) ( a a | b ) + ( a a | b ) + ( a a | b ) + ( a | b b ) + ( a a $(aa|b)^+ = R_0$$(a|bb)^+ = R_1$$(R_0R^*_1R_0)$$(aa|b)^+(aa|b)^+$ ( a a | b ) + ( a | b b ) + ( a | b b ) + ( a a | b ) $(aa|b)^+(a|bb)^+(aa|b)^+$$(aa|b)^+(a|bb)^+(a|bb)^+(aa|b)^+$

En otros términos, la expresión regular bajo expresión regular se puede describir usando la operación de composición. Deje ser un lenguaje regular bajo el alfabeto y . Considere los idiomas regulares debajo de algún alfabeto . Entonces, para cada palabra de , sustituimos la letra por el idioma correspondiente , entonces y la unión de todos esos idiomas, forma el lenguajeΣ | Σ | = n L σ 1 , L σ 2 , … , L σ n Δ w L w [ i ] = σ j L σ j w = w [ 1 ] w [ 2 ] … w [ k ] → L w [ 1 ] L w [ 2 ] … $L$$\Sigma$$|\Sigma| = n$$L_{\sigma_1}, L_{\sigma_2}, \ldots, L_{\sigma_n}$$\Delta$$w$$L$$w[i] = \sigma_j$$L_{\sigma_j}$$w = w[1]w[2]\ldots w[k] \to L_{w[1]}L_{w[2]}\ldots L_{w[k]}$$comp(L,L_1,\ldots,L_n)$. Entonces, el nivel de expresión regular bajo expresión regular es solo el número de operaciones de composición que se utilizaron. Y los lenguajes regulares están cerrados bajo operación de composición.

Pero hay algunos resultados interesantes obtenidos por una técnica que es muy parecida a la que usted describe. Me refiero a la operación . es un tipo de lenguaje, que cada palabra de los rendimientos de tales árbol, que cada camino en ese árbol mentiras en . Para obtener más información al respecto, consulte el documento . $\delta-$$\delta(L)$$\delta(L)$$L$