<p>For a fixed alphabet <span class="math-container">$\Sigma$</span>, the blow-up is at most polynomial.</p>
<p>First, given a regular expression <span class="math-container">$r$</span>, it is straightforward to construct an expression <span class="math-container">$\tilde r$</span> using the operators <span class="math-container">$a\in\Sigma$</span>, <span class="math-container">$+$</span>, <span class="math-container">$\cdot$</span>, <span class="math-container">$(-)^+$</span>, and <span class="math-container">$\let\nul\varnothing\nul$</span> such that
<span class="math-container">$$L(\tilde r)=L(r)\let\bez\smallsetminus\bez\{\let\ep\varepsilon\ep\}$$</span>
recursively, by putting <span class="math-container">$\tilde a=a$</span>, <span class="math-container">$\tilde\epsilon=\tilde\nul=\nul$</span>, <span class="math-container">$\let\wt\widetilde\wt{r+s}=\tilde r+\tilde s$</span>, <span class="math-container">$\wt{r^*}=\tilde r^+$</span>, and
<span class="math-container">$$\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}.$$</span>
Unless <span class="math-container">$L(r)\subseteq\{\ep\}$</span>, we can subsequently eliminate <span class="math-container">$\nul$</span> using <span class="math-container">$\nul+r=r+\nul=r$</span>, <span class="math-container">$\nul\cdot r=r\cdot\nul=\nul^+=\nul$</span>. Thus, if <span class="math-container">$r$</span> is a regular expression such that <span class="math-container">$\ep\notin L(r)\ne\nul$</span>, then <span class="math-container">$\tilde r$</span> is an <span class="math-container">$\ep$</span>-free regular expression as defined in the question such that <span class="math-container">$L(r)=L(\tilde r)$</span>.</p>
<p>In general, the size of <span class="math-container">$\tilde r$</span> may be exponential in the size of <span class="math-container">$r$</span>, but the <em>depth</em> of <span class="math-container">$\tilde r$</span> is linear in the depth of <span class="math-container">$r$</span>. Crucially, every regular expression <span class="math-container">$r$</span> of size <span class="math-container">$n$</span> has an equivalent regular expression <span class="math-container">$s$</span> of depth <span class="math-container">$O(\log n)$</span> by Theorem 6.2 in</p>
<blockquote>
<p>Moses Ganardi, Markus Lohrey: <em>A universal tree balancing theorem</em>, ACM Transactions on Computation Theory 11 (2019), no. 1, article no. 1, 25 pp, doi <a href="https://doi.org/10.1145/3278158" rel="noreferrer">10.1145/3278158</a>. Preprint <a href="https://arxiv.org/abs/1704.08705" rel="noreferrer">arXiv:1704.08705</a> [cs.CC].</p>
</blockquote>
<p>Then <span class="math-container">$\tilde s$</span> also has depth <span class="math-container">$O(\log n)$</span>, hence size <span class="math-container">$2^{O(\log n)}=n^{O(1)}$</span>.</p>

CC BY-SA 4.0
2021-07-08T19:59:23.660Z
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.
Denis
CC BY-SA 4.0
2021-07-08T17:50:13.217Z
2021-07-08T18:51:33.440Z
2021-07-08T18:51:33.440Z
Emil Jeřábek
<p>Consider regular expressions on some alphabet <span class="math-container">$\Sigma$</span>, without the empty word: <span class="math-container">$$e,f:=a\in\Sigma\mid e\cdot f \mid e+f\mid e^+$$</span></p>
<p>These <span class="math-container">$\varepsilon$</span>⁻free expressions can define all regular languages that do not contain the empty word (<span class="math-container">$\varepsilon$</span>-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 <span class="math-container">$\varepsilon$</span>), that accepts an <span class="math-container">$\varepsilon$</span>-free language, into an <span class="math-container">$\varepsilon$</span>-free expression?</p>
<p>It could seem that for instance the expression <span class="math-container">$a_0(a_1+\varepsilon)(a_2+\varepsilon)(a_3+\varepsilon)\dots(a_n+\varepsilon)$</span> 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 <span class="math-container">$e,f$</span> for <span class="math-container">$(a_1+\varepsilon)\dots(a_{n/2}+\varepsilon)$</span> and <span class="math-container">$(a_{n/2+1}+\varepsilon)\dots(a_n+\varepsilon)$</span> respectively, and returns <span class="math-container">$(e+f+e\cdot f)$</span>. This will produce an expression <span class="math-container">$E$</span> of quadratic size only, and we can return <span class="math-container">$a_0+a_0E$</span>.</p>
<p>It seems non-trivial however to generalize this idea to any input expression, if possible.</p>
<p>Do you know of any reference on the subject?</p>

CC BY-SA 4.0
2021-07-05T13:59:04.967Z
Maybe $ab(c+\varepsilon)ab^2(c+\varepsilon)ab^3(c+\varepsilon)\dots$?
xavierm02
CC BY-SA 4.0
2021-07-05T16:39:29.990Z
@xavierm02 That's $ab(ca+a)b^2(ca+a)b^3(ca+a)\dots$.
Emil Jeřábek
CC BY-SA 4.0
2021-07-05T18:21:45.103Z
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?
Shaull
CC BY-SA 4.0
2021-07-05T22:11:28.210Z
@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$
Denis
CC BY-SA 4.0
2021-07-06T04:55:34.047Z
@Denis - yeah, you're right. But you have to admire my persistence in suggesting answers to your questions, knowing full well anything I think of, you probably thought of already :)
Shaull
CC BY-SA 4.0
2021-07-09T20:44:09.450Z
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)
https://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.
Hermann Gruber
<reference-request><regular-expressions>
Succinctness of regular expressions with empty word
Denis
# Succinctness of regular expressions with empty word

(Asked by: username_0 on 2021-07-05)

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?

**Tags:** reference-request, regular-expressions

> **Comments:**
> **username_1**: Maybe $ab(c+\varepsilon)ab^2(c+\varepsilon)ab^3(c+\varepsilon)\dots$?  
> **username_2**: @username_1 That's $ab(ca+a)b^2(ca+a)b^3(ca+a)\dots$.  
> **username_3**: 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?  
> **username_0**: @username_3 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$  
> **username_3**: @username_0 - yeah, you're right. But you have to admire my persistence in suggesting answers to your questions, knowing full well anything I think of, you probably thought of already :)  
> **username_4**: 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) https://doi.org/10.1016/0304-3975(96)00028-X Thanks  @username_2 for pointing out my mistake - my answer will delete itself within 5 seconds, I will retain only this comment.  

---

## 1 answers

### Answer by username_2 on 2021-07-08. Score: 9 | Accepted answer

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](https://doi.org/10.1145/3278158). Preprint [arXiv:1704.08705](https://arxiv.org/abs/1704.08705) [cs.CC].

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

> **Comments:**
> **username_0**: 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.  

---

