On Some Parameters Occurring in Certain Effective Constructions of Grammars

Abstract

J. Ostravský considered two classes of languages – B^S and B^C – and described an effective construction assigning a pure grammar G^j_k(V,L) to any j∈{s,c}, to any language (V,L), and to any integer k⩾1. He proved that (V,L)∈B^j if and only if there exists k₀⩾1 such that G^j_k(V,L) = G^j_k0(V,L) for any k⩾k₀. The least integer k₀ with this property is a complexity measure of the language (V,L)∈B^j. Besides this complexity measure, we study another one introduced in connection with the above mentioned construction. We compare the complexity of languages with the complexity of languages obtained by usual operations from the given ones.