New answers tagged

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