Efficient Learning of Regular Languages Using Teacher-Supplied Positive Samples and Learner-Generated Queries

We present a new algorithm for efficient learning of regular languages from examples and queries. A reliable teacher who knows the unknown regular grammar G (or is able to determine if certain strings are accepted by the grammar) will guide the learner in achieving the goal of inferring an equivalent grammar $\mbox{G}^{*}$. The teacher provides the learner with a structurally complete set of positive examples belonging to the unknown grammar G. Using this information the learner constructs a canonical automaton which accepts exactly those examples. The canonical automaton defines a set of grammars which are ordered on a lattice to form the hypothesis space. A bi-directional search algorithm is used to systematically search the lattice for the solution G*. While searching for the solution, the learner interacts with the teacher by posing queries. The teacher\u27s responses enable the learner to eliminate one or more points on the lattice which do not correspond to the correct solution. After successive eliminations, when only one lattice element remains, the process is terminated and that element is accepted as the solution G*. The inferred grammar is proven to be equivalent to original grammar G