1 - Introduction

Summary

The grand aim of all science is to cover the greatest number of empirical facts by logical deduction from the smallest number of hypotheses or axioms.

Albert Einstein

Todos os problemas são insolúveis. A essência de haver um problema é não haver uma solução. Procurar um facto significa não haver um facto. Pensar é não saber existir.

Fernando Pessoa, Livro do Desassossego, 107

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.