On a Construction of Context-free Grammars

Article type: Research Article

Authors: Martinek, Pavel

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.

Keywords: grammatical inference, context-free grammar, context-free language, identification in the limit

Journal: Fundamenta Informaticae, vol. 44, no. 3, pp. 245-264, 2000