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?

  • $\begingroup$ Maybe $ab(c+\varepsilon)ab^2(c+\varepsilon)ab^3(c+\varepsilon)\dots$? $\endgroup$
    – xavierm02
    Jul 5 at 13:59
  • 2
    $\begingroup$ @xavierm02 That's $ab(ca+a)b^2(ca+a)b^3(ca+a)\dots$. $\endgroup$ Jul 5 at 16:39
  • 1
    $\begingroup$ 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? $\endgroup$
    – Shaull
    Jul 5 at 18:21
  • 3
    $\begingroup$ @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$ $\endgroup$
    – Denis
    Jul 5 at 22:11
  • 1
    $\begingroup$ 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. $\endgroup$ 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

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)}$.

  • $\begingroup$ 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. $\endgroup$
    – Denis
    Jul 8 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.