The study of learnability of the class of k-acceptable languages on Gold’s learning model
Anuchit Jitpattanakul* [a] , and Athasit Surarerks[a]* Author for corresponding; e-mail address: januchit@yahoo.com
Volume: Vol.40 No.2 (APRIL 2013)
Research Article
DOI:
Received: 9 December 2011, Revised: -, Accepted: 5 April 2012, Published: -
Citation: Jitpattanakul A. and Surarerks A., The study of learnability of the class of k-acceptable languages on Gold’s learning model, Chiang Mai Journal of Science, 2013; 40(2): 248-260.
Abstract
The study of learnability of formal languages is an attractive topic in grammatical inference. Many classes of the formal languages have been theoretically investigated their learnability from some presentations. These obtained results are applicable for some real-world problems such as speech recognition, protien-motif classification. However, the study is limited to formal languages defined over unordered alphabets. In this article, we focus our attention on formal languages that are defined over ordered alphabets called k-acceptable languages. We theoretically show that the class of this language is not learnable by using only positive examples. By using both positive and negative examples, we show that the class of k-acceptable languages is learnable in the limit from polynomial time and data.