# Minimal context-free grammar for a regular language

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.