Learning Non-deterministic Finite Automata from Queries and Counterexamples
Takashi Yokomori · 1994
Abstract In the recent theoretical research activity of inductive learning, in particular, of inductive inference, Angluin has introduced the model of learning called minimally adequate teacher (MAT), that is, the model of learning via membership queries and equivalence queries, and has shown that the class of regular languages is efficiently learnable using deterministic finite automata (DFAs) (Angluin 1987b). More specifically, she has presented an algorithm which, given any regular language, learns from MAT a minimum DFA accepting the target in time polynomial in the number of states of the minimum DFA and the maximum length of any counterexample provided by the teacher. The MAT learning model is reasonably accepted for the following reasons. First, the limit of the learning capability from only given example data is well-recognized. Actually, Gold shows that the time complexity of learning consistent DFAs from given data is computationally intractable (Gold 1978). Hence, learning models from more than given data are required to study the feasible learnability. On the other hand, there is another motivation for introducing the MAT learning model which comes from a more practical viewpoint. Suppose one wants to construct an expert system (or knowledge system) and (s)he is trying to collect inference rules by interviewing human experts.