Operational complexity and right linear grammars

Abstract

For a regular language L, let Var(L) be the minimal number of nonterminals necessary to generate L by right linear grammars. Moreover, for natural numbers k1,k2,…,kn and an n-ary regularity preserving operation f, let gVarf(k1,k2,…,kn) be the set of all numbers k such that there are regular languages L1,L2,…,Ln such that Var(Li)=ki for 1≤i≤n and Var(f(L1,L2,…,Ln))=k. We completely determine the sets gVarf for the operations reversal, Kleene-closures + and ∗, and union; and we give partial results for product and intersection.