Chiang Mai Journal of Science

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.