Nonterminal Complexity of Some Operations on Context-Free Languages

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.