A Polynomial Time Incremental Algorithm for Regular Grammar Inference

Abstract

<p>We present an efficient incremental algorithm for learning regular grammars from labeled examples and membership queries. This algorithm is an extension of Angluin's {\em ID} procedure to an incremental framework. The learning algorithm is intermittently provided with labeled examples and has access to a knowledgeable teacher capable of answering membership queries. Based on the observed examples and the teacher's responses to membership queries, the learner constructs a deterministic finite automaton (DFA) with which all examples observed thus far are consistent. When additional examples are observed, the learner modifies this DFA suitably to encompass the information provided by the new examples. In the limit this algorithm is guaranteed to converge to a minimum state DFA corresponding to the target regular grammar. We prove the convergence of this algorithm in the limit and analyze its time and space complexities.</p>