Grammatical inference

As H. Fernau and C. de la Higuera pointed out [16], there is a number of good reasons for formal language specialists to be interested in the field of grammatical inference, among others ... 

Grammatical inference deals with formalisms describing formal languages, such us formal grammars, automata, etc. 

Grammatical inference tries to give mathematical descriptions of the classes of languages that can be learned by a concrete learning algorithm. 

Most of grammatical inference research has been focused on learning regular and context-free languages. Although these are the basic classes of the Chomsky hierarchy, it has been proved that even to learn these classes is already too hard under certain learning paradigms. Next, we review the main formal models proposed in this field and some of the main learnability results obtained. 

Clark, A. Grammatical inference and first langnage acquisition. In Workshop on Psychocomputational Models of Human Language Acquisition, Geneva, pp. 25-32 (2004)... 

Sosfk, P., Stybnar, L. Grammatical inference of colonies. In Paun, G., Salomaa, A. (eds.) New Trends in Formal Languages. LNCS, vol. 1218. Springer, Heidelberg (1997)... 

The aim of grammatical inference is to leam models of languages from sample sentences in these languages. A sentence can be any structured composition of primitive elements or symbols, though the most common type of composition is concatenation. So we infer grammar and the corresponding representation is an automaton. 

Parekh, R., Nichitiu, C.M., Honavar, V. A polynomial time incremental algorithm for learning DFA. In Proceeding of International Colloquium on Grammatical Inference Algorithms and Apphcations, pp. 37-49 (1998)... 

Example 3-7 In grammatical inference, the concept class aimed at is the set of languages over some alphabet. Examples of a language are sentences of that language. Hypotheses may be expressed as grammars, acceptors, regular expressions, and so on. 

---