Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

Non-ambiguous:

$ab^*c$
$(a|b)c$
$ab^+c$
$ab?c$
$a(b|c)$
$c(ab)^*ccc$
$acc^*d$
$abc|bcd$

Ambiguous:

$abc^*$
$abc^+$
$abc?$
$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.

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

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
2  
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.) –  Raphael Jan 22 '13 at 19:28
1  
The question asks for a property of expressions, not languages. –  reinierpost Jan 23 '13 at 15:03
1  
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".) –  Skeptic Jan 23 '13 at 16:18
1  
@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. –  Khaur Jan 23 '13 at 16:28
1  
@Kaveh As Raphael stated, prefix-freeness is necessary, but not all prefix-free regular languages satisfy Skeptic's idea of non-ambiguity. –  Khaur Jan 24 '13 at 10:40
show 10 more comments

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.

share|improve this answer
    
acc* would be "ambiguous". –  Skeptic Jan 23 '13 at 16:21
    
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? –  reinierpost Jan 23 '13 at 16:48
    
both acc* and ac*c would be "ambiguous", but not acc*d. –  Skeptic Jan 23 '13 at 16:49
    
OK, then it's none of these. You really have to tell more about what you mean by "ambiguity". –  reinierpost Jan 23 '13 at 16:50
    
I realize now that I should have asked about the language and not the expression. –  Skeptic Jan 23 '13 at 16:53
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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