Nonterminal Complexity of Some Operations on Context-Free Languages
Jürgen Dassow, Ralf Stiebe · 2007
Abstract: We investigate context-free languages with respect to the measure Var of descriptional complexity, which gives the minimal number of nonterminals which is necessary to generate the language. Especially, we consider the behaviour of this measure with respect to operations. For given numbers c1, c2,..., cn and an n-ary operation τ on languages we discuss the range of Var(τ(L1, L2,..., Ln)) where, for 1 ≤ i ≤ n, Li is a context-free language with Var(Li) = ci. The operation under discussion are the six AFL-operations union, concatenation, Kleene-closure, homomorphisms, inverse homomorphisms and intersections by regular sets. 1