Are there any algorithms for solving exactly the following question? Given a regular language L, represented as a finite automaton say, what is a CFG with minimal number of nonterminals that generates the language L?


Note that a CFG with $n$ non-terminals can generate a language consisting of a single (highly repetitive) word of length $2^n$, something that only a FSA with $2^n$ states will recognize. Hence in some case your minimal CFG will be much smaller than any FSA for $L$.

Actually, one can get much bigger reduction "factors". Take a deterministic Turing machine $M$ that happens to halt. One can define a CFG $G_M$ that recognizes exactly all words that are not (encodings of) the single run of $M$. This is a language $L$ consisting of all words except the single run, hence a regular language. The size of $G_M$ is polynomial in the size of $M$ while the size of a FSA for $L$ can be enormous (i.e., the single run can be very long, think Busy Beaver). Thus a regular language that requires an enormous FSA can be represented by a tiny grammar.

Your question evokes some notion of compression of regular languages. Indeed, the most popular schemes for compressing long words can be seen as some kind of CFGs, see J. A. Storer and T. G. Szymanski, Data compression via textual substitution.

| cite | improve this answer | |
  • $\begingroup$ Yes it is reduces to the minimal/smallest grammar problem when L is finite. But I don't know if any work has been done on this when it is infinite. $\endgroup$ – Alexander Clark Jul 4 '13 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.