# Ambiguity of regular expressions

Some regular expressions are ambiguous. Some are not. a*b* is unambiguous for example. Expression a*a* is ambiguous but it can be written in the unambiguous form 'a*`. The answer to this question gives an algorithm for deciding whether a regular expression is ambiguous.

1. Is there an algorithm for finding an equivalent unambiguous form of any given RE?
2. Are there REs that are inherently ambiguous?

(This question seems relevant by title; not by content)

• Coming to think about it, there is a more direct, recursive algorithm, much like the one that decides ambiguity. Recursively, expression $r_1|r_2$ is ambiguous, replace it by $r_3|r_4|r_5$ where $r_3=r_1 \wedge r_2$, $r_4=r_2 \ r_1$, $r_5=r_2\r_1$. – Yossi Gil Apr 11 at 4:45
• @YossiGil As far as I can tell, intersection and complement only help to disambiguate alternatives. How does your recursive algorithm disambiguage concatenation expressions $r_1r_2$ (which may be ambiguous if there are distinct $x,y\in L(r_1)$, $u,v\in L(r_2)$ such that $xu=yv$) or $r^*$? – Emil Jeřábek Apr 11 at 10:35
• @HermannGruber: You are of course right. I see it differently, while implementing a DSL for regular expressions, in which matching (language recognition) is done by an LL parser. So, given an re $r$, trivially convert it into an equivalent grammar $G=G(r)$. We know $G$ is LL, so the DSL can be implemented by recursive descent. My DSL should allow extended REs in which negation is yet another RE constructor. I hope to implement negation by a modification to the recursive descent algorithm. The normalized form is useful for correcting and ambiguous $r$ provided by user. – Yossi Gil Apr 11 at 14:29