It is known that nondeterministic finite automata (NFA) minimization is
computationally hard. For instance, finding a minimal NFA given a deterministic
finite automaton is PSPACE-complete (Jiang and Ravikumar, 1993). Also, it is
known that minimal NFAs are not identifiable in the limit from polynomial time
and data (Higuera, 1997) and they are also not efficiently approximable (Gruber
and Holzer, 2007). However, there are some successful induction algorithms
presented in the literature, including DeLeTe2 (Denis et al., 2004) and
Nondeterministic Regular Positive Negative Inference (Alvarez et al., 2005), or
the state merging methods discussed in (Coste and Fredouille, 2003; Garcia et
al., 2008). Moreover, there are also solutions transforming the induction
problem into the constraint satisfaction problem (CSP), which we follow here.