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, end(G)(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 end(G)(n) is constant. Yet, we improve on this by showing that if L(G) is nonregular then end(G)(n) = Omega(infinity)(log n). 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.
context-free grammars complexity measures