This research deals with the design of new grammatical inference algorithms for regular languages; of particular interest are strategies using state merging as their main feature. Both deterministic and non-deterministic state merging variations have been studied from a theoretical point of view. As a result, an efficient non-deterministic merging states method has been proposed; besides, it has been proved that grammatical inference for regular languages based on state merging (both deterministic and non-deterministic) converges in the limit independently of the order in which the merging is done. This proof is very interesting, since among other reasons, it allows to state the convergence in the limit of the EDSM (Evidence Driven States Merging) strategy, which is broadly known in the literature as a heuristic. Given that the proof also considers non-deterministic merging, this result may be effective in the design of new convergent inference algorithms for non-deterministic automata.

On the practical side, this research proposes several grammatical inference algorithms for regular languages, all of which converge in the limit. These algorithms explore both deterministic and non-deterministic state merging methods and take advantage of the information obtained from inclusion relations between derivatives of each state of an automaton. Six new algorithms are proposed; four of them yield deterministic automata while the remaining two produce non-deterministic automata. The results of experimental comparisons between the new algorithms and well known reference ones like RPNI, red-blue or DeLeTe2, show that the proposed algorithms are able to get significantly smaller hypothesis than its counterparts while the recognition rates are comparable or slightly lower. Furthermore, for some of the proposed algorithms, these results are obtained using methods of a lower temporal complexity than those used in the reference algorithms.