Learning Finite State Machines
Colin de la Higuera
In: FSMNLP 2009, 18-21 Jul 2009, Pretoria, South Africa.
The terms grammatical inference and grammar induction
both seem to indicate that techniques aiming at building grammatical formalisms when given some information about a language are not concerned with automata or other finite state machines. This is far from true, and many of the more important results in grammatical inference rely heavily on automata formalisms, and particularly on determinism.
We survey here some of the main ideas and results in the field.