On a construction of context-free gramma

• Autorzy: Martinek, P.
• Języki publikacji: EN

Abstrakty

EN

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. It is proved that G(j,k) are equivalent for all j > j(o), k > k(o) with some positive integers j(o), k(o). Moreover, the equivalences among these grammars can be recognized on the basis of involved nonterminals and productions only.

Słowa kluczowe

EN

grammatical inference problem; context-free grammar; context-free language; identification in the limit

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2000
• Tom: Vol. 44, Nr 3
• Strony: 245-264
• Opis fizyczny: bibliogr. 18 poz.

Twórcy

autor

Martinek, P.

• Department of Mathematics, Mendel University of Agriculture and Forestry, Brno, Zemedelska 3, 613 00 Czech Republic,