Abstract:
The article considers the problem of 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.
Fulltext:
PDF file (371 kB)