Is there a name/interest for regular languages that have a non-ambiguous ending?

Question

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.

Answer 1

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.

Answer 2

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.