<p>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:</p>
<p> R. Book, S. Even, S. Greibach and G. Ott, <a href="https://doi.org/10.1109/T-C.1971.223204" rel="nofollow noreferrer">Ambiguity in graphs and expressions</a>, IEEE Transactions on Computers 20(2) (1971) 149–153. </p>
<p>See also this question over at MO for more details and a reference: <a href="https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous">https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous</a></p>

CC BY-SA 4.0
2021-04-11T04:45:07.280Z
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
CC BY-SA 4.0
2021-04-11T08:30:19.150Z
Hehe okay. But regular expressions only have the operators union, catenation and star. To simulate intersection and complement with ordinary regular expressions, you would probably use algorithms that are at least as complex as the one described above, right? If you are fine with generalized regular expressions, your construction is the easy way out. But keep in mind that converting a generalized one back to an ordinary regular expression will incur a tower-of-exponentials blowup in size. Simple decision problems like emptiness share a similar doom in this model.
Hermann Gruber
CC BY-SA 4.0
2021-04-11T10:35:04.580Z
@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
CC BY-SA 4.0
2021-04-11T14:10:12.870Z
I believe the algorithm described in the reference can handle this.
Yossi Gil
CC BY-SA 4.0
2021-04-11T14:29:10.953Z
@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
CC BY-SA 4.0
2021-04-11T15:26:18.793Z
Alright, if you only need to solve the word problem, then generalized regular expressions are fine. The algorithm in the reference does not use generalized regular expressions anyway.
Hermann Gruber
CC BY-SA 4.0
2021-04-10T19:31:03.143Z
2021-04-18T21:15:00.537Z
2021-04-18T21:15:00.537Z
Hermann Gruber
<p>Some regular expressions are ambiguous. Some are not. <code>a*b*</code> is unambiguous for example. Expression <code>a*a*</code> is ambiguous but it can be written in the unambiguous form 'a*`. The answer to <a href="https://math.stackexchange.com/questions/608993/check-if-a-regex-is-ambiguous">this question</a> gives an algorithm for deciding whether a regular expression is ambiguous.</p>
<ol>
<li>Is there an algorithm for finding an equivalent unambiguous form of any given RE?</li>
<li>Are there REs that are inherently ambiguous?</li>
</ol>
<p>(This <a href="https://cstheory.stackexchange.com/questions/19102/ambiguity-in-regular-and-context-free-languages">question</a> seems relevant by title; not by content)</p>

<fl.formal-languages><regular-expressions>
Ambiguity of regular expressions
Yossi Gil
# Ambiguity of regular expressions

(Asked by: username_0 on 2021-04-10)

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](https://math.stackexchange.com/questions/608993/check-if-a-regex-is-ambiguous) 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](https://cstheory.stackexchange.com/questions/19102/ambiguity-in-regular-and-context-free-languages) seems relevant by title; not by content)

**Tags:** fl.formal-languages, regular-expressions


---

## 1 answers

### Answer by username_1 on 2021-04-10. Score: 13 | Accepted answer

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](https://doi.org/10.1109/T-C.1971.223204), IEEE Transactions on Computers 20(2) (1971) 149–153.

See also this question over at MO for more details and a reference: <https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous>

> **Comments:**
> **username_0**: 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$.  
> **username_1**: Hehe okay. But regular expressions only have the operators union, catenation and star. To simulate intersection and complement with ordinary regular expressions, you would probably use algorithms that are at least as complex as the one described above, right? If you are fine with generalized regular expressions, your construction is the easy way out. But keep in mind that converting a generalized one back to an ordinary regular expression will incur a tower-of-exponentials blowup in size. Simple decision problems like emptiness share a similar doom in this model.  
> **username_2**: @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^*$?  
> **username_0**: I believe the algorithm described in the reference can handle this.  
> **username_0**: @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.  
> **username_1**: Alright, if you only need to solve the word problem, then generalized regular expressions are fine. The algorithm in the reference does not use generalized regular expressions anyway.  

---

