Passively Learning Finite Automata

We provide a survey of methods for inferring the structure of a finite automaton from passive observation of its behavior. We consider both deterministic automata and probabilistic automata (similar to Hidden Markov Models). While it is computationally intractible to solve the general problem exactly, we will consider heuristic algorithms, and also special cases which are tractible. Most of the algorithms we consider are based on the idea of building a tree which encodes all of the examples we have seen, and then merging equivalent nodes to produce a (near) minimal automaton. Contents 1 Introduction 4 1.1 Applications of automaton inference : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 1.2 Why PFAs instead of other probabilistic models? : : : : : : : : : : : : : : : : : : : : : : : : : 5 1.3 The input to/output from the algorithms : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 1.4 Batch vs. online algorithms : : : : : : : : : : : : : : : : : : : : : :..