Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Is there a name/interest for regular languages that have a non-ambiguous ending?

, ,
Problem Detail:

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.

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.