17
$\begingroup$

When investigating regular languages, regular expressions are obviously a useful characterisation, not least because they are amenable to nice inductions. On the other hand ambiguity can get in the way of some proofs.

Every regular language is recognized by an unambiguous context-free grammar (take a deterministic automaton which recognises it, and make a production $R \rightarrow tS$ for every edge $R \stackrel{t}{\rightarrow} S$ in the DFA, and $R \rightarrow \epsilon$ for every accepting state $R$).

On the other hand, the natural "grammar" for a regular language is its regular expression. Can these be made unambiguous?

To be precise, let's define a parse for a regular expression (this is I think a natural definition, but not one I've seen named before).

  • $x$ is an $x$-parse of $x$, if $x$ is a symbol or $x=\varepsilon$
  • $(y, 0)$ is an $R\cup R'$-parse of $x$, if $y$ is an $R$-parse of $x$
  • Similarly, $(y,1)$ is an $R\cup R'$-parse of $x$, if $y$ is an $R'$-parse of $x$
  • $(y_1, y_2)$ is an $RR'$-parse for $x_1x_2$, if $y_i$ is an $R$-parse for $x_i$ for $i=1,2$
  • $[]$ is an $R^*$-parse for $\varepsilon$
  • $[y_1, y_2, \dots, y_n]$ is an $R^*$-parse of $x_1x_2\cdots x_n$, if $y_i$ is an $R$-parse for $x_i$ for $1 \le i \le n$

In short, the parses of a string tell us how a regular expression matches a string if it does.

A regular expression $R$ is unambiguous if, for every $x \in L(R)$, there is only one $R$-parse of $x$.

Given a regular expression, is there an unambiguous regular expression which matches the same language?
$\endgroup$

2 Answers 2

16
$\begingroup$

There's a standard construction of a regular expression from a DFA: define an expression R(i,j,k) for the language of strings that take state i to state j of the DFA while using intermediate states that belong only to the subset of states from state 1 to state k, as follows.

  • R(i,j,0) is [xyz...] where x, y, z etc are the symbols that occur as labels of transitions from state i to state j (there can be no intermediate states). If there is no such transition then R(i,j,0)=0 (the expression for the empty language).
  • Similarly, R(i,i,0) is e + [xyz...] where e is the expression that represents the empty string.
  • For k > 0, R(i,j,k) is R(i,j,k-1) + R(i,k,k-1) R(k,k,k-1)* R(k,j,k-1). That is, any string that takes you from i to j using intermediate states up to k either goes from i to j without going through k, or can be parsed into a sequence of substrings that go from i to k, k back to itself zero or more times, and then k to j.
  • The regular expression for the whole language is then the sum of the expressions R(1,i,n) where i is one of the accepting states.

The first two of these rules obviously give you unambiguous expressions, the third is unambiguous because there's only one way of parsing the string into substrings as described, and the fourth is unambiguous because any given string can only go to a single accepting state. Therefore, the final regular expression constructed in this way is unambiguous.

$\endgroup$
4
  • $\begingroup$ I think this is essentially the same construction as I have seen before, but this presentation is simpler while at the same time making the unambiguity clear. Thank you! The next question this raises for me is whether it can be done without the exponential explosion of the RE -> DFA step. A nice problem for me to think about. $\endgroup$
    – Max
    Nov 7, 2010 at 13:29
  • $\begingroup$ Is there a reference for this construction? Is this different from one-unambiguous regular expressions? $\endgroup$ Jul 15, 2014 at 18:30
  • 1
    $\begingroup$ @jmite: First, the requested reference: R. Book, S. Even, S. Greibach and G. Ott, Ambiguity in graphs and expressions, IEEE Transactions on Computers 20(2) (1971) 149–153. To your 2nd question: yes, one-unambiguous regular expressions are those whose position automaton is deterministic; they capture only a subset of the regular languages. For instance, the languages $(a+b)^*a(a+b)^n$, for $n\ge 1$, cannot be denoted by any one-unambiguous regular expression whatsoever. See A. Brüggemann-Klein and D. Wood, One-unambiguous regular languages, Information and Computation 140(2) (1998) 229 – 253. $\endgroup$ Oct 22, 2014 at 19:41
  • $\begingroup$ For reference, this "standard construction" is en.wikipedia.org/wiki/Kleene%27s_algorithm $\endgroup$
    – a3nm
    Feb 15, 2023 at 10:23
3
$\begingroup$

Regarding your question about disambiguation without exponential increase: if you're willing to move to generalized regular expressions (regular expressions with the complement and intersection operators as primitives, rather than exponential-blowup-inducing derived operations), then yes: assuming longest-match-convention on the Kleene star the only source of ambiguity will be the alternation (vertical bar) construct, and you can disambiguate every instance of this by simply turning "a|b" into "a|(b&~a)" ("a or b-and-not-a").

Note that adding intersection and complementation does not alter the class of languages which may be defined. The languages which can be defined are still exactly the regular languages.

I think this suggests that you probably can't disambiguate in general without exponential blowup because disambiguation is "pretty similar to" (vague term, I know) intersection with the complement.

Here's a nice paper which presents many of the results needed above.

$\endgroup$
2
  • 2
    $\begingroup$ I did not intend to use the longest match rule. My intuition is that one can make alternation unambiguous with neither a complement operator nor exponential blowup by factoring out the common part of the alternatives. $\endgroup$
    – Max
    Dec 5, 2010 at 1:09
  • $\begingroup$ Thanks for the nice reference though! $\endgroup$
    – Max
    Dec 5, 2010 at 1:10

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.