Abstract:
The article considers constructing minimal deterministic finite automaton recognizing a prefix-code of a given cardinality over the alphabet $\{0,1\}$. The considered problem is proved to be equivalent to the problem of finding the shortest addition-chain ending with a given number. Several interesting properties of the desired minimal finite automaton are proved, and the identical problem concerning Moore automata is discussed.
Keywords:prefix code, finite-state machine, Moore automaton, addition chain.