New answers tagged regular-expressions
9
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 $\...
Top 50 recent answers are included
