In chapter 4, the computational capabilities of discrete-time recurrent neural networks were discussed in terms of their equivalence or their parallelism to various classes of automata. In particular, automata such as deterministic finite-state automata and Turing machines may be seen as language acceptors. Chapter 4 also discussed a generative way of defining formal languages, grammars, and describes the relationships among languages, grammars and automata.
If a given application involves data sequences which can be represented as strings of symbols from a finite alphabet and a sequence processing task (chapter 3) that involves classification of these sequences into two or more classes or sets (languages) or recognition of those sequences that belong to a single class of interest, then it may be the case that language acceptors such as finite-state automata may be capable of performing the task or that grammars may be used to express the rules that define the sequences belonging to one of the classes (languages).
Many sequence recognition/classification applications may be reduced to this formulation. In this case, it may be interesting to learn a sequence-processing task by inferring the rules of the grammar(s) or the structure of the accepting automaton (automata) from samples (learning sets) of classified sequences (strings).
Grammatical inference is the usual name given to the process of learning (inferring) a grammar from a set of sample strings, and, in view of the equivalences that may be established between grammars and automata, the task of learning an automaton from a set of sample strings may also be called grammatical inference.
Grammatical inference is usually formulated in terms of learning recognition or classification tasks from sets in which all strings are labeled as belonging to one or another class (language); however, tasks such as learning a finite-state machine that transduces (translates) strings from one language into strings from another language or learning a probabilistic finite-state machine that generates strings following a certain probability distribution may also be formulated as grammatical inference tasks.