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.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ 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). $\endgroup$– Klaus DraegerOct 8, 2012 at 15:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Regular languages are closed under union, concatenation and star, so regular expressions under regular expressions describes regular languages. So, regex, that describe regex, that describe regex still describe family of regular languages, and you can continue that process as long, as you want.
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 .
