Efficient construction of a finite-state automaton from a set of strings

Traditional construction of dictionaries from strings in form of finite automata involves constructing a trie and then minimizing it. Although such method is correct, the size of the intermediate product - the trie - can be enormous. Two methods that will be presented (for sorted and unsorted input) construct a minimal automaton in a single phase by adding new strings one by one and minimizing the resulting automaton on-the-fly. The advantages of incremental construction are the minimal intermediate memory requirements and dramatical reduction in the total construction time of these minimal dictionaries in comparison to other methods.