Effective Construction of Grammars for Languages of Two Particular Classes

Abstract

In this paper we solve inference problem for languages on two particular classes B^C, B^S. For any language (V,L) ∈ B^j, j ∈ {s,c}, and any natural number i, we define a grammar G^j_i(V,L) in an effective way. We prove that (V,L) ∈ B^j iff there exists a natural number i₀ such that G^j_i(V,L) = G^j_i0(V,L) for any i ⩾ i₀; the grammar G^j_i0(V,L) generates (V,L).