# Succinctness of regular expressions with empty word

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?

• Maybe $ab(c+\varepsilon)ab^2(c+\varepsilon)ab^3(c+\varepsilon)\dots$? Jul 5 at 13:59
• @xavierm02 That's $ab(ca+a)b^2(ca+a)b^3(ca+a)\dots$. Jul 5 at 16:39
• In your example, you don't actually need to split in the middle - anywhere would work, so you can split after the first concatenation. Maybe this can be used as a basis for an inductive argument? Jul 5 at 18:21
• @Shaull are you sure ? I believed if you always split at the first concatenation you will end up with an exponential formula, since you duplicate the formula returned on input of size $n-1$ Jul 5 at 22:11
• The following paper deals with a similar but different question: Djelloul Ziadi: Regular Expression for a Language without Empty Word. Theor. Comput. Sci. 163(1&2): 309-315 (1996) doi.org/10.1016/0304-3975(96)00028-X Thanks @Emil Jeřábek for pointing out my mistake - my answer will delete itself within 5 seconds, I will retain only this comment. Jul 9 at 20:44

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
Then $$\tilde s$$ also has depth $$O(\log n)$$, hence size $$2^{O(\log n)}=n^{O(1)}$$.
• Thanks ! Indeed this rewriting with a depth of $O(\log n)$ corresponds to "balancing the tree" of the expression, which can be viewed as a general formulation of the example I gave. Jul 8 at 19:59