Formal language theory has been developed and studied consistently over the past 50 years. Because of their importance in so many fields, strings and tools to manipulate them have been studied with special care, leading to the specific topic of stringology. Usual definitions and results can therefore be found in several text books.

We re-visit these objects here from a pragmatic point of view: grammatical inference is about learning grammars and automata which are then supposed to be used by programs to deal with strings. Their advantage is that we can parse with them, compare them, compute distances… Therefore, we are primarily interested in studying how the strings are organised: knowing that a string is in a language (or perhaps more importantly out of the language) is not enough. We will also want to know how it belongs or why it doesn't belong. Other questions might be about finding close strings or building a kernel taking into account their properties. The goal is therefore going to be to organise the strings, to put some topology over them.

Notations

We start by introducing here some general notations used throughout the book.

In a definition ifdef is a definition ‘if’.

The main mathematical objects used in this book are letters and strings.

We describe algorithm LSTAR, introduced by Dana Angluin, which has inspired several variants and adaptations to other classes of languages.

The minimally adequate teacher

A minimally adequate teacher (MAT) is an Oracle that can give answers to membership queries and strong equivalence queries. We analysed in Section 9.2 the case where you want to learn with less.

The main algorithm that works in this setting is called LSTAR. The general idea of LSTAR is:

1. • find a consistent observation table (representing a DFA),

2. • submit it as an equivalence query,

3. • use the counter-example to update the table,

4. • submit membership queries to make the table closed and complete,

5. • iterate until the Oracle, upon an equivalence query, tells us that the correct language has been reached.

The observation table we use is analogous to that described in Section 12.3, so we will use the same formalism here.

An observation table

An observation table is a specific tabular representation of an automaton. An example is given in Table 13.1(a).

If we suppose that the data have been obtained through sampling, that means we have (or at least believe in) an underlying probability over the strings. In most cases we do not have a description of this distribution, and we describe three plausible learning settings.

The first possibility is that the data are sampled according to an unknown distribution, and that whatever we learn from, the data will be measured with respect to this distribution. This corresponds to the well-known PAC-learning setting (probably approximately correct).

The second possibility is that the data are sampled according to a distribution itself defined by a grammar or an automaton. The goal will now no longer be to classify strings but to learn this distribution. The quality of the learning process can then be measured either while accepting a small error (most of the time, since a particular sampling can have been completely corrupted!), or in the limit, with probability one. One can even hope for a combination of both these criteria.

There are other possible related settings that we only mention briefly here: an important one concerns the case where the distribution in the PAC model is computable, without being generated by a grammar or an automaton. The problem remains a classification question for which we have only restricted the class of admissible distributions.

Instead of defining a language as a set of strings, there are good reasons to consider the seemingly more complex idea of defining a distribution over strings. The distribution can be regular, in which case the strings are then generated by a probabilistic regular grammar or a probabilistic finite automaton. We are also interested in the special case where the automaton is deterministic.

Once distributions are defined, distances between the distributions and the syntactic objects they represent can be defined and in some cases they can be conveniently computed.

Distributions over strings

Given a finite alphabet Σ, the set Σ* of all strings over Σ is enumerable, and therefore a distribution can be defined.

‘Learning from an informant’ is the setting in which the data consists of labelled strings, each label indicating whether or not the string belongs to the target language.

Of all the issues which grammatical inference scientists have worked on, this is probably the one on which most energy has been spent over the years. Algorithms have been proposed, competitions have been launched, theoretical results have been given. On one hand, the problem has been proved to be on a par with mighty theoretical computer science questions arising from combinatorics, number theory and cryptography, and on the other hand cunning heuristics and techniques employing ideas from artificial intelligence and language theory have been devised.

There would be a point in presenting this theme with a special focus on the class of context-free grammars with a hope that the theory for the particular class of the finite automata would follow, but the history and the techniques tell us otherwise. The main focus is therefore going to be on the simpler yet sufficiently rich question of learning deterministic finite automata from positive and negative examples.

A zillion grammatical inference years ago, some researchers in grammatical inference thought of writing a book about their favourite topic. If there was no agreement about the notations, the important algorithms, the central theorems or the fact that the chapter about learning from text had to come before or after the one dealing with learning from an informant, there were no protests when the intended title was proposed: the art of inferring grammars. The choice of the word art is meaningful: like in other areas of machine learning, what counted were the ideas, the fact that one was able to do something complicated like actually building an automaton from strings, and that it somehow fitted the intuition that biology and images (some typical examples) could be explained through language. This ‘artistic’ book was never written, and since then the field has matured.

When writing this book, I hoped to contribute to the idea that the field of grammatical inference has now established itself as a scientific area of research. But I also felt I would be happy if the reader could grasp those appealing artistic aspects of the field.

The artistic essence of grammatical inference was not the only problem needing to be tackled; other questions also required answers…

Bilanguages

There are many cases where the function one wants to learn doesn't just associate a label or a probability with a given string, but should be able to return another string, perhaps even written using another alphabet. This is the case in translation, of course, between two ‘natural’ languages, but also of situations where the syntax of a text is used to extract some semantics. And it can be the situation in many other tasks where machine or human languages intervene.

There are a number of books and articles dealing with machine translation, but we will only deal here with a very simplified setting consistent with the types of finite state machines used in the previous chapters; more complex translation models based on context-free or lexicalised grammars are beyond the scope of this book.

The goal is therefore to infer special finite transducers, those representing subsequential functions.

Rational transducers

Even if in natural language translation tasks the alphabet is often the same for the two languages, this needs not be so. For the sake of generality, we will therefore manipulate two alphabets, typically denoted by Σ for the input alphabet and Γ for the output one.

A language is a set of strings, and a string either belongs to a language or does not. An alternative is to define a distribution over the set of all strings, and in some sense the probability of a string in this set is indicative of its importance in the language. This distribution, if learnt from data, can in turn be used to disambiguate, by inding the most probable string corresponding to a pattern, or to predict by proposing the next symbol for a given preix.

We propose in this chapter to investigate ways of learning distributions representable by probabilistic automata from strings. No extra knowledge is usually provided. In particular the structure of the automaton is unknown. The case where the structure is known corresponds to the problem of probability estimation and is discussed in Chapter 17.

We only work in this chapter with deterministic probabilistic finite automata.

The problem of inducing, learning or inferring grammars has been studied now for some time, either as a purely mathematical problem, where the goal is to find some hidden function, or as a more practical problem of attempting to represent some knowledge about strings or trees through a typical representation of sets of trees and strings, such as an automaton or a grammar.

The field

Historically, one can trace back the problem to three main different sources: the first is computational linguistics, the second is inductive inference and the third is pattern recognition. The historical lineage, to be fair, requires us to discuss the important contribution of at least two other fields, not entirely independent of the three historical ones: machine learning and bio-informatics.

(Computational) linguistics

The key question of language acquisition (meaning the acquisition by a child of its first language), when considered as a formal language learning task, takes its root in Noam Chomsky's pioneering work.

In order to get a better grasp of the problem of learning grammars, we need to understand both how the individual objects we are trying to infer are shaped and how the set of these objects is structured. This will enable us to formally state learnability and non-learnability results, but also to identify and study the search space and the operators to move around this space; in turn, this will enable us to develop new heuristics.

The first results are mainly negative: if to learn a grammar you have to solve some intractable combinatorial problem, then only wild guessing is going to allow you to identify or infer correctly, but then you are relying on luck, not on convergence probability. This sort of result is usually obtained by reductions: typically, we show that if a well-known hard problem can be solved via a learning algorithm (perhaps with some error, so it may depend on a randomised version), it will mean that something is wrong. The learning algorithm cannot do what it promises to do.

But working on the combinatorics of automata and grammars also helps us to build intuitions that contribute to designing learning processes.

In the different combinatorial methods described in the previous chapters, the main engine to the generalisation process is something like:

‘If nothing tells me not to generalise, do it.’

For example, in the case where we are learning from an informant, the negative data provide us with the reason why one should not generalise (which is usually performed by merging two states). In the case of learning from text, the limitations exercised by the extra bias on the grammar class are what avoid over-generalisation.

But as a principle, the ‘do it if you are allowed’ idea is surely not the soundest. Since identification in the limit is achieved through elimination of alternatives, and an alternative can only be eliminated if there are facts that prohibit it, the principle is mathematically sound but defies common sense.

There are going to be both advantages and risks to considering a less optimistic point of view, which could be expressed somehow like:

‘If there are good reasons to generalise, then do it.’

On one hand, generalisations will be justified through the fact that there is some positive ground, some good reason to make them.

From the results of the previous section, it appears quite clear that DFAs cannot be identified in the limit from text. At which point, if the chosen task is indeed to learn DFAs from text, we need either some help (perhaps some extra information about the strings or some structure) or else we will have to add an extra bias and reduce the class of automata.

It should be noted that adding more bias consists also of adding some more information (something like ‘we know that the automaton has this property’).

Window languages

It is well known that regular languages correspond to the class of languages that can be parsed using a bounded memory. But what happens is that this memory is bounded a priori. We may consider the subclass of languages for which parsing uses only a memory of size k, meaning that the next letter to be read will depend only on the knowledge of the k — 1 previous characters.