The basic idea is to have one or more symbol that clearly indicate the end. For example:




$acc^*$ or $ac^*c$

An alternative definition of a non-ambiguous ending would be that the corresponding DFA can have multiple final states, but none of them can have a outgoing transition.

  • 3
    $\begingroup$ Try formalising your definition of non-ambiguous a bit more. For example, would $(abca)^*bc$ be considered non-ambiguous? If and if not, why? $\endgroup$ – Khaur Jan 22 '13 at 13:15
  • $\begingroup$ I have added an alternative definition of a non-ambiguous ending. $\endgroup$ – Rhangaun Jan 24 '13 at 17:31
  • 1
    $\begingroup$ This alternate definition corresponds to prefix-freeness. $\endgroup$ – Khaur Jan 25 '13 at 9:40

According to your alternative definition, you're looking for a language such that $u\in L\Rightarrow \forall v\neq\epsilon, uv\notin L$ (where $\epsilon$ denotes the empty string).

That property defines a useful kind of language in coding, called prefix-free codes. Note that this language class doesn't include nor is included in regular languages.

So what you're looking for is the intersection of those two classes. That would be a prefix-free regular language.

As for the interest, it seems to have some, since a google search returned this research paper.

  • 2
    $\begingroup$ While prefix-freeness is certainly necessary for "non-ambiguity" as discussed here, is it sufficient? (I think it is; I think your answer should give a justification why it is either.) $\endgroup$ – Raphael Jan 22 '13 at 19:28
  • 1
    $\begingroup$ The question asks for a property of expressions, not languages. $\endgroup$ – reinierpost Jan 23 '13 at 15:03
  • 1
    $\begingroup$ Well, I clearly didn't take enough time to ponder the proper wording of my question, but I was not entirely convinced myself of what I was really looking for. At this point, I do think its prefix-freeness (i.e. abc|bcd wouldn't be "ambiguous".) $\endgroup$ – Rhangaun Jan 23 '13 at 16:18
  • 1
    $\begingroup$ @Skeptic Now that your mind is clearer on what you were looking for, you may want to edit your question to make it clearer for future users who stumble on the question (maybe add a bit of context as well). Also, please note that the example $(abca)^*bc$ that I mentioned in a comment on the question is prefix-free. $\endgroup$ – Khaur Jan 23 '13 at 16:28
  • 1
    $\begingroup$ @Kaveh As Raphael stated, prefix-freeness is necessary, but not all prefix-free regular languages satisfy Skeptic's idea of non-ambiguity. $\endgroup$ – Khaur Jan 24 '13 at 10:40

Are you merely looking for unicity of the last character?

In that case, you may mean a property such as:

  • the regular expression ends with a character (it is xc for some expression x and character c)
  • the language described by the regular expression ends with a character (it is Lc for some regular language L and character c)

They are different properties: acc* meets 2 but not 1.

Or are you looking for a stronger property, that must also apply elsewhere in the expression?

In that case, you may be looking for determinism. Determinism is the property of never having to backtrack and retry while trying to parse (match) a string. It is usually defined assuming parsing from left to right, so it applies to unicity of prefixes rather than suffixes; and it is usually defined for finite automata or context-free grammars rather than regular expressions (but not always - see, e.g., this paper about deterministic regular expressions). In that case, you may be looking for a property such as:

  • the reverse of the regular expression is deterministic

Here, the reverse is the regular expression obtained by swapping all concatenation arguments, e.g. the reverses of ab*c, (a|b)c, ab+c, ab?c, abc*, a(b|c), abc+, abc? are cb*a, c(a|b), cb+a, cb?a, c*ba, (b|c)a, c+ba, c?ba, respectively.

I don't know a name for any of these properties.

  • $\begingroup$ acc* would be "ambiguous". $\endgroup$ – Rhangaun Jan 23 '13 at 16:21
  • $\begingroup$ acc* does not meet the third property; ac*c does; so that doesn't tell me which property (if any of these) you mean. Is acc*d "ambiguous", according to you? $\endgroup$ – reinierpost Jan 23 '13 at 16:48
  • $\begingroup$ both acc* and acc would be "ambiguous", but not accd. $\endgroup$ – Rhangaun Jan 23 '13 at 16:49
  • $\begingroup$ OK, then it's none of these. You really have to tell more about what you mean by "ambiguity". $\endgroup$ – reinierpost Jan 23 '13 at 16:50
  • $\begingroup$ I realize now that I should have asked about the language and not the expression. $\endgroup$ – Rhangaun Jan 23 '13 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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