Limits of Pure Grammars with Monotone Productions

Article type: Research Article

Authors: Martinek, Pavel

Affiliations: Faculty of Forestry and Wood Technology, Mendel University of Agriculture and Forestry, Zemědělská 3, 613 00 Brno, Czech Republic

Abstract: The grammatical inference problem is solved for a class of languages which can be generated by pure grammars with non-shortening productions. Necessary and sufficient condition for determination whether a language belongs to this class is formulated and proved. Finally, an algorithm for assigning a pure grammar to any language from the class is described.

Keywords: grammatical inference problem, pure (or special) grammar, limits of pure grammars, language generated by pure grammars, 1-grammatizable language, monotone (or non-shortening) productions, pure grammar with monotone (or non-shortening) productions

DOI: 10.3233/FI-1998-33304

Journal: Fundamenta Informaticae, vol. 33, no. 3, pp. 265-280, 1998