Abstract:
A non-deterministic automaton M may accept a string in A* along more than one path. An 'ambiguity Detection' automaton D(M) will be constructed which accepts precisely those strings that are accepted by M along more than one path. Each set C of non-null strings over an alphabet A will be called a code. The elements of C* will be called messages over the code C. For each regular code C, let M = M(C) be the minimal deterministic automaton recognizing C. An associated non-deterministic automaton M' will be constructed that recognizes C*. The D(M') will then be constructed. It will recognize those messages in C* which can be segmented (deciphered) in more than one way. Consequently, C is a uniquely decipherable (UD) code if and only if the language L(D(M')) is empty. Moreover, for an arbitrary regular code C, C* \ L(D(M')) is the set of all messages which are uniquely segmentable (decipherable) into a string of code words. The language A* \ L(D(M')) is the unique maximal language in A* having the property that each of its strings can be segmented into words in C. Since A* \ L(DM')) is regular, for any regular language L, it can be decided whether the code C is UD relative to L by deciding whether L is contained in A* \ L(D(M')).
The following code concepts will be discussed in a parallel manner - leading to decision procedures for their relative versions: the prefix, suffix, infix, and solid code concepts. Regarding the concepts: solid code & comma free code, we have: C is solid iff it is solid relative to A*; and C is comma free iff it is solid relative to C*. These developments provide the context in which the 'join code hierarchy' (introduced previously) was developed - in which the comma free codes constitute the level one join codes.
For each regular code C the set of messages in C* that can be segmented (decyphered) in only one way into a sequence of words in C will be shown to be regular.