# Regular expressions of families of regular expressions

I was reading about the Star Height Problem and noticed that Eggan's family of regular expressions follows a simple pattern which can be described by a regular expression. My question is: are there any interesting results about regular expressions which describe families of regular expressions? Can this process be continued further, so you have a regex describing a family of regexes each of which in turn describes a family of regexes? Just a thought.

• What kind of description are you talking about? Both the Eggan and Dejean-Schützenberger families of REs have features that makes them non-regular (parentheses of unbounded depth; furthermore the indices in the Eggan case, and the growing a- and b-blocks in the D-S case). Oct 8 '12 at 15:04

Here, by «describe» I mean that first, you have just regex, like $(aa|b)^+ = R_0$ and regex $(a|bb)^+ = R_1$, than you describe regex level 1 like $(R_0R^*_1R_0)$, this regex describe languages $(aa|b)^+(aa|b)^+$, $(aa|b)^+(a|bb)^+(aa|b)^+$, $(aa|b)^+(a|bb)^+(a|bb)^+(aa|b)^+$, … and so on.
In other terms regex under regex can be described using composition operation. Let $L$ be a regular language under alphabet $\Sigma$ and $|\Sigma| = n$. Consider regular languages $L_{\sigma_1}, L_{\sigma_2}, \ldots, L_{\sigma_n}$ under some alphabet $\Delta$. So, for each word $w$ from $L$ we substitute letter $w[i] = \sigma_j$ by corresponding language $L_{\sigma_j}$, so $w = w[1]w[2]\ldots w[k] \to L_{w[1]}L_{w[2]}\ldots L_{w[k]}$ and union of all such languages, forms language $comp(L,L_1,\ldots,L_n)$. So, level of regex under regex is just number of composition operations, that were used. And regular languages are closed under composition-operation.
But there are some interesting results obtained by technique that's very closed to the one, that you describe. I mean the $\delta-$operation. $\delta(L)$ is a such language, that every word from $\delta(L)$ yields by such tree, that every path in that tree lies in $L$. To learn more about it see the paper .