On a Construction of Context-free Grammars

Abstract

The grammatical inference problem is solved for the class of context-free languages. A context-free language is supposed to be given by means of all its strings. Considering all strings of length bounded by k, context-free grammars G_{j,k} with 1≤j<k are constructed. A~continual increasing of the index~$k$ leads to an~infinite sequence (G_{j,k})_{j<k}. It is proved that G_{j,k} are equivalent for all j≥j_0, k≥k_0 with some positive integers j_0, k_0. Moreover, the equivalences among these grammars can be recognized on the basis of involved nonterminals and productions only.