# Tag Info

13

Yes, every regular expression can be converted into an unambiguous one by converting to a DFA and then to a regular expression. And no, there aren't any inherently ambiguous regular languages in the sense described in the question. This is a classic result in automata theory:  R. Book, S. Even, S. Greibach and G. Ott, Ambiguity in graphs and 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 $\... 5$\beta(E_1)$is the language$s^nx,s^{n+1}x$. This language is straightforwardly not regular, by the pumping lemma. If we assume that the language is regular, the pumping lemma tells us that there must exist some$p, q$such that for all$n \ge p$,$s^{n+q}x,s^{n+1}x$is also in the language. This is false, meaning that the language is not regular. A similar ... 2 To simplify, let$D$be the domain of$T$and let$R = \{\epsilon\} \cup (\Sigma^* \setminus \Sigma^*D\Sigma^*)$. Then by definition $$N(T) = Id_R \quad \text{and} \quad R^{obl}(T) = N(T)(TN(T))^*.$$ Here is a formal way to justify your idea. Let$(u,v) \in \Sigma^* \times \Sigma^*$. By definition,$(u,v) \in R^{obl}(T)$if and only if$(u,v)\$ can be ...

1

Hyperscan is a high-performance multiple regex matching library that uses hybrid automata techniques to allow simultaneous matching of large numbers of regular expressions across streams of data. They explained their approach here: https://www.hyperscan.io/2015/10/20/match-regular-expressions Apparently, they didn't find a fast algorithm (in the worst case) ...

Only top voted, non community-wiki answers of a minimum length are eligible