FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME
Paweł Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey O. Shallit · International Journal of Foundations of Computer Science · 2010
We give an O(n + t) time algorithm to determine whether an NFA with n states and t transitions accepts a language of polynomial or exponential growth. Given an NFA accepting a language of polynomial growth, we can also determine the order of polynomial growth in O(n+t) time. We also give polynomial time algorithms to solve these problems for context-free grammars.