View Related Documents

Abstract

Grammatical inference consists in learning formal grammars for unknown languages when given learning data. Classically this data is raw: strings that belong to the language and eventually strings that do not. We present in this paper the possibility of learning when presented with additional information such as the knowledge that the hidden language belongs to some known language, or that the strings are typed, or that specific patterns have to/can appear in the strings. We propose a general setting to deal with these cases and provide algorithms that can learn deterministic finite automata in these conditions. Furthermore the number of examples needed to correctly identify can diminish drastically with the quality of the added information. We show that this general setting can cope with several well known learning tasks.
This work was done when the second author visited the Departamento de Lenguajes y Sistemas Informáticos of the University of Alicante, Spain. The visit was sponsored by the Spanish Ministry of Education.

Fulltext Preview

Image of the first page of the fulltext document