INDUCTIVE INFERENCE OF MONOGENIC PURE CONTEXT-FREE LANGUAGES

A subclass of context-free languages, called pure context-free languag es, which is generated by context-free grammar with only one type of s ymbol (i.e., terminals and nonterminals are not distinguished), is int roduced and the problem of identifying from positive data a restricted class of monogenic pure context-free languages (mono-PCF languages, i n short) is investigated. The class of mono-PCF languages is incompara ble to the class of regular languages. In this paper we show that the class of mono-PCF languages is polynomial time identifiable from posit ive data. That is, there is an algorithm that, given a mono-PCF langua ge L, identifies from positive data, a grammar generating L, called a monogenic pure context-free grammar (mono-PCF grammar, in short) satis fying the property that the time for updating a conjecture is bounded by O(N-3), where N is the sum of lengths of all positive data provided . This is in contrast with another result in this paper that the class of PCF languages is not identifiable in the limit from positive data.