A regularity condition for context-free grammars

We define a complexity measure on context-free grammars called end. Roughly speaking, for a context-free grammar G, endG(n measures the distance of variables from the ends of sentential forms along the derivations of words in L(G) of length n. We prove in a constructive way the regularity of L(G) whenever endG(n) is constant. Yet, we improve on this by showing that if L(G) is nonregular then endG(n) = Ω∞(logn). We establish the optimality of such bound. Finally, we show that, in case of unambiguous context-free grammars, the end lower bound for generating nonregular languages turns out to be linear.