On Some Parameters Occurring in Certain Effective Constructions of Grammars

Article type: Research Article

Authors: Păun, Gheorghe^a | Novotný, Miroslav^b

Affiliations: [a] University of Bucharest | [b] Czechoslovak Academy of Sciences, Branch Brno

Abstract: J. Ostravský considered two classes of languages – BS and BC – and described an effective construction assigning a pure grammar Gjk(V,L) to any j∈{s,c}, to any language (V,L), and to any integer k⩾1. He proved that (V,L)∈Bj if and only if there exists k0⩾1 such that Gjk(V,L) = Gjk0(V,L) for any k⩾k0. The least integer k0 with this property is a complexity measure of the language (V,L)∈Bj. 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.

Keywords: pure grammar, s-grammatizable language, c-grammatizable language, minimum k zero of the language, maximum preequality of the language, s-faithful language, c-faithful language

DOI: 10.3233/FI-1987-10105

Journal: Fundamenta Informaticae, vol. 10, no. 1, pp. 69-80, 1987