Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-09-26
Computer Science
Formal Languages and Automata Theory
Scientific paper
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.
No associations
LandOfFree
A Regularity Measure for Context Free Grammars does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Regularity Measure for Context Free Grammars, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Regularity Measure for Context Free Grammars will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-689819