Language Learning with Characteristic Examples and Membership Queries
Hiroshi Sakamoto, 比呂志 坂本 · QIR (Kyushu University Institutional Repository) (Kyushu University) · 1995
This paper introduces the notion of characteristic examples for languages and shows that the notion contributes to language learning in polynomial time. A characteristic example of a language L is a string of L which includes, in a sense, sufficient information to represent the language L. We show that any context-free language can be divided into a finite set of languages each of which has a characteristic example. We prove that it is solvable whether or not a context-free language has a characteristic example. Then, we propose a learning model with membership queries and characteristic examples for the class of parenthesis languages. We prove that, for this class, our learning algorithm runs in a polynomial time in the size of a minimal parenthesis grammar which generates the target language and in the length of a longest characteristic example given to the algorithm. 1