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 $uin LRightarrow forall vneqepsilon, uvnotin 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
