Effective Construction of Grammars for Languages of Two Particular Classes

Article type: Research Article

Authors: Ostravský, Jan

Affiliations: Faculty of Technology Gottwaldov, VUT Brno

Abstract: In this paper we solve inference problem for languages on two particular classes BC, BS. For any language (V,L) ∈ Bj, j ∈ {s,c}, and any natural number i, we define a grammar Gji(V,L) in an effective way. We prove that (V,L) ∈ Bj iff there exists a natural number i0 such that Gji(V,L) = Gji0(V,L) for any i ⩾ i0; the grammar Gji0(V,L) generates (V,L).

Keywords: special generalized grammar, special grammar, language generated by the (generalized) special grammar, norms, monotone productions or c-productions, context-free productions or s-productions, special grammar with s-productions, special grammar with c-productions, languages of the classes B^C and B^S, reducing operator, fragment of the language, relation T_i(V,L), relation T^j_i(V,L), special grammar G^j_i(V,L)

DOI: 10.3233/FI-1985-8206

Journal: Fundamenta Informaticae, vol. 8, no. 2, pp. 235-252, 1985