Characteristic Sets for Learning k-Acceptable Languages

Abstract

Learnability of languages is a challenging problem in the domain of formal language identification. It is known that the efficiency of a learning technique can be measured by the size of some good samples (representative or distinctive samples) formally called a characteristic set. Our research focuses on the characteristic set of k-acceptable languages. We proposed a Gold-style learning algorithm called KRPNI which applied the grammatical inference technique to identify a language and expressed it by a k-DFA. In this paper, we study the existence of such characteristic sets. Our theoretical results show that there exists a polynomial characteristic set for a k-acceptable language. It is found that the size of the characteristic set depends on the value of k, instead of the size of an alphabet.