Minimal finite automata from finite training sets
Bennett Setzer · 2008
This paper describes a solution to the following problem: Given a finite set of strings A over an alphabet Σ and a positive integer n, find a deterministic finite automaton (DFA) with a minimal number of states that recognizes the strings in the given set but does not recognize any other strings of length less than n. It turns out that, for some sets of strings A and integers n, the DFA is not uniquely determined.