Succinctness of regular expressions with empty word

Question

Consider regular expressions on some alphabet $\Sigma$, without the empty word: $$e,f:=a\in\Sigma\mid e\cdot f \mid e+f\mid e^+$$

These $\varepsilon$⁻free expressions can define all regular languages that do not contain the empty word ($\varepsilon$-free languages). Does it come at a cost in terms of expression size ? In particular, is there an exponential blow-up for translating a classical regular expression (with $\varepsilon$), that accepts an $\varepsilon$-free language, into an $\varepsilon$-free expression?

It could seem that for instance the expression $a_0(a_1+\varepsilon)(a_2+\varepsilon)(a_3+\varepsilon)\dots(a_n+\varepsilon)$ would require such an exponential blow-up. But actually it looks like we can use a recursive algorithm that splits the product in the middle, computes expressions $e,f$ for $(a_1+\varepsilon)\dots(a_{n/2}+\varepsilon)$ and $(a_{n/2+1}+\varepsilon)\dots(a_n+\varepsilon)$ respectively, and returns $(e+f+e\cdot f)$. This will produce an expression $E$ of quadratic size only, and we can return $a_0+a_0E$.

It seems non-trivial however to generalize this idea to any input expression, if possible.

Do you know of any reference on the subject?

Answer 1

For a fixed alphabet $\Sigma$, the blow-up is at most polynomial.

First, given a regular expression $r$, it is straightforward to construct an expression $\tilde r$ using the operators $a\in\Sigma$, $+$, $\cdot$, $(-)^+$, and $\let\nul\varnothing\nul$ such that $$L(\tilde r)=L(r)\let\bez\smallsetminus\bez\{\let\ep\varepsilon\ep\}$$ recursively, by putting $\tilde a=a$, $\tilde\epsilon=\tilde\nul=\nul$, $\let\wt\widetilde\wt{r+s}=\tilde r+\tilde s$, $\wt{r^*}=\tilde r^+$, and $$\wt{r\cdot s}=\tilde r\cdot\tilde s\underbrace{{}+\tilde r}_{\kern-1em\text{if }\ep\in L(s)\kern-1em}\overbrace{{}+\tilde s}^{\kern-1em\text{if }\ep\in L(r)\kern-1em}.$$ Unless $L(r)\subseteq\{\ep\}$, we can subsequently eliminate $\nul$ using $\nul+r=r+\nul=r$, $\nul\cdot r=r\cdot\nul=\nul^+=\nul$. Thus, if $r$ is a regular expression such that $\ep\notin L(r)\ne\nul$, then $\tilde r$ is an $\ep$-free regular expression as defined in the question such that $L(r)=L(\tilde r)$.

In general, the size of $\tilde r$ may be exponential in the size of $r$, but the depth of $\tilde r$ is linear in the depth of $r$. Crucially, every regular expression $r$ of size $n$ has an equivalent regular expression $s$ of depth $O(\log n)$ by Theorem 6.2 in

Moses Ganardi, Markus Lohrey: A universal tree balancing theorem, ACM Transactions on Computation Theory 11 (2019), no. 1, article no. 1, 25 pp, doi 10.1145/3278158. Preprint arXiv:1704.08705 [cs.CC].

Then $\tilde s$ also has depth $O(\log n)$, hence size $2^{O(\log n)}=n^{O(1)}$.