Nonterminal Complexity of Some Operations on Context-Free Languages

Article type: Research Article

Authors: Dassow, Jürgen | Stiebe, Ralf

Affiliations: Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, PSF 4120, D-39016 Magdeburg, Germany. E-mails: dassow@iws.cs.uni-magdeburg.de; stiebe@iws.cs.uni-magdeburg.de

Abstract: We investigate context-free languages with respect to the measure Var of descriptional complexity, which gives the minimal number of nonterminals necessary to generate a language. More specifically, we consider the behaviour of this measure with respect to language-theoretic operations. For given numbers c_1, c_2, …, c_n and an n-ary operation τ on language, we discuss the range of Var (τ(L_1,L_2,…L_n)) where for 1 ⩽i⩽n, L_i is a context-free language with Var (L_i) = c_i. The operations under discussion are the six AFL-operations: union, concatenation, Kleene-closure, homomorphisms, inverse homomorphisms and intersections by regular sets.

Keywords: context-free languages, descriptional complexity, AFL operations

Journal: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 35-49, 2008