  Parikh's theorem states that every Context Free Language (CFL) has the same
Parikh image as that of a regular language. A finite state automaton accepting
such a regular language is called a Parikh-equivalent automaton. In the worst
case, the number of states in any non-deterministic Parikh-equivalent automaton
is exponentially large in the size of the Context Free Grammar (CFG). We
associate a regularity width d with a CFG that measures the closeness of the
CFL with regular languages. The degree m of a CFG is one less than the maximum
number of variable occurrences in the right hand side of any production. Given
a CFG with n variables, we construct a Parikh-equivalent non-deterministic
automaton whose number of states is upper bounded by a polynomial in $n
(d^{2d(m+1)}), the degree of the polynomial being a small fixed constant. Our
procedure is constructive and runs in time polynomial in the size of the
automaton. In the terminology of parameterized complexity, we prove that
constructing a Parikh-equivalent automaton for a given CFG is Fixed Parameter
Tractable (FPT) when the degree m and regularity width d are parameters. We
also give an example from program verification domain where the degree and
regularity are small compared to the size of the grammar.
