[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.

Asked By : Rhangaun

Answered By : Khaur

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9091

 Ask a Question

 Download Related Notes/Documents