10
$\begingroup$

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)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
13
$\begingroup$

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, 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

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$
    – Yossi Gil
    Commented Apr 11, 2021 at 4:45
  • $\begingroup$ 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. $\endgroup$
    – Hermann Gruber
    Commented Apr 11, 2021 at 8:30
  • 2
    $\begingroup$ @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^*$? $\endgroup$
    – Emil Jeřábek
    Commented Apr 11, 2021 at 10:35
  • $\begingroup$ I believe the algorithm described in the reference can handle this. $\endgroup$
    – Yossi Gil
    Commented Apr 11, 2021 at 14:10
  • 1
    $\begingroup$ @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. $\endgroup$
    – Yossi Gil
    Commented Apr 11, 2021 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.