<p>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$.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Busy_beaver">Busy Beaver</a>). Thus a regular language that requires an enormous FSA can be represented by a tiny grammar.</p>

<p>Your question evokes some notion of <em>compression of regular languages</em>. 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,
<a href="http://dx.doi.org/10.1145/322344.322346"><em>Data compression via textual substitution</em></a>.</p>

CC BY-SA 3.0
2013-07-04T14:52:45.057Z
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.
Alexander Clark
CC BY-SA 3.0
2013-07-03T16:10:01.783Z
2013-07-03T16:57:17.323Z
2013-07-03T16:57:17.323Z
phs
<p>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?</p>

<automata-theory><context-free-languages>
Minimal context-free grammar for a regular language
Alexander Clark
# Minimal context-free grammar for a regular language

(Asked by: username_0 on 2013-07-03)

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?

**Tags:** automata-theory, context-free-languages

---

## 1 answers

### Answer by username_1 on 2013-07-03. Score: 6

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](http://en.wikipedia.org/wiki/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*](http://dx.doi.org/10.1145/322344.322346).

> **Comments:**
> **username_0**: 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.  

---

