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_i₀(V,L) for any i ⩾ i₀; the grammar G^j_i₀(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 reducing operator fragment of the language

Get full access to this article

View all access options for this article.