<p>The following inapproximability result is known (Theorem 17 in Gruber/Holzer/Wolfsteiner, DLT 2018):</p>
<p>Given a context-free grammar of size <span class="math-container">$s$</span> generating a finite
language <span class="math-container">$L$</span>, it is impossible to approximate the minimum grammar size of <span class="math-container">$L$</span> within a factor of <span class="math-container">$o(s^\frac{1}{7})$</span>, unless P = NP.</p>
<p>Hermann Gruber, Markus Holzer, and Simon Wolfsteiner. <a href="http://www.hermann-gruber.com/data/dlt-18-revised.pdf" rel="nofollow noreferrer">On Minimal Grammar Problems for Finite Languages.</a> In Mizuho Hoshi and Shinnosuke Seki, editors, 22nd International Conference on Developments in Language Theory (DLT 2018), Tokyo, Japan, volume 11088 of Lecture Notes in Computer Science, pages 342--353. Springer, September 2018.</p>
<p>Notice that the number of words in the reduction is exponential in their length. To my knowledge, there are no research papers that address the exact case of polynomially many words.
But the theorem shows the important point, in that it disproves the intuition that there may be a &quot;quantity discount&quot; effect if we want one minimal grammar for many words.</p>
<p>(A late answer; I hope it will still prove useful for somebody.)</p>

CC BY-SA 4.0
2023-11-18T21:37:42.943Z
2023-11-24T12:26:59.413Z
2023-11-24T12:26:59.413Z
Hermann Gruber
<p>If $\ell$ and $k$ are fixed, there are only finitely many possible problem instances, so you can write a program that has a hardcoded table of all possible instances and their solutions.  Consequently, the complexity will be $O(1)$, if you consider $\ell$ and $k$ as fixed and look at the asymptotics as $n$ increases.</p>

<p>Why are there only finitely many possible problem instances?  Because when $\Sigma$ and $\ell$ are fixed and $\Sigma$ is finite, there are only finitely many subsets of $\Sigma^1 \cup \Sigma^2 \cup \Sigma^3 \cup \cdots \cup \Sigma^{\ell}$.</p>

CC BY-SA 3.0
2016-03-28T19:59:27.630Z
While you are technically correct, isn't this lookup table massive for any reasonable $\ell$ and $k$?

Specifically, you have $\sum_{i=1}^\ell k^i=(k (k^\ell-1))/(k-1)$ possible strings, and thus $2^{\sum_{i=1}^\ell k^i}$ possible problem instances.

It's my fault for not specifying that I would like a reasonable dependence on $\ell$ and $k$, but I figured a solution should be fairly reasonable for small $\ell$ and $k$ (say less than 15), yet your lookup table for $\ell=3$ and $k=3$ has 549,755,813,888 possible elements.
Phylliida
CC BY-SA 3.0
2016-03-28T03:49:56.430Z
2016-03-28T03:49:56.430Z
D.W.
<p>Worst case you have a Kolmogorov complexity issue where you have chosen half of the $k^l$ words at random. Since it is random your CFG has to take $O(k^l)$ space since it cannot compress.</p>

CC BY-SA 3.0
2016-03-29T08:14:33.613Z
Your answer is talking about the size of the smallest CFG.  The question seems to be asking about the running time of an algorithm to find the smallest CFG.  Therefore, while it's a valid comment, it doesn't seem to answer the question that was asked.
D.W.
CC BY-SA 3.0
2016-03-28T15:17:31.263Z
2016-03-28T15:17:31.263Z
Chad Brewbaker
<p>Problem:</p>

<p>Given a finite set of strings $\{x_1, x_2, ..., x_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a_1, a_2, ..., a_k\}$, find the minimal context free grammar that recognizes all of these strings.</p>

<p>If $k$ is a constant, and $n = poly(\ell)$, what can one say about this problem's complexity as $\ell$ grows?</p>

<p>This seems similar to the <a href="https://en.wikipedia.org/wiki/Smallest_grammar_problem" rel="noreferrer">smallest grammar problem</a>, which is NP-Hard for the optimization problem. However it is a little different because of having multiple strings, since now one needs to recognize each string independently instead of recognizing all of them at once. The smallest grammar problem is clearly a subset of this, but for small $\ell$ this might be much easier to solve, I'm not sure.</p>

<p>Is there a way to approximately solve this problem efficiently?</p>

CC BY-SA 3.0
2016-03-29T08:58:01.733Z
Almost certainly not what you're looking for, but have you seen the [Sequitur](https://en.wikipedia.org/wiki/Sequitur_algorithm) algorithm?  It's a heuristic for a related problem.
D.W.
CC BY-SA 3.0
2016-03-29T15:22:07.310Z
Oo that is really close/useful for my purposes. You're right it doesn't solve this problem but thanks for the reference.
Phylliida
CC BY-SA 4.0
2023-11-21T08:49:30.870Z
How do you measure the size of a CFG? There are lots of different measures, including
total number of occurrences of variables and terminals on both sides
of all productions in the grammar; number of variable occurrences on
both sides of all productions; number of productions; number of distinct variables. (I doubt it
will make a great difference to the asymptotic complexity)
Martin Berger
CC BY-SA 4.0
2023-11-21T08:54:37.727Z
What do you mean by grammar the *"recognizes all of these strings"*?
If you mean that $\{x_1,x_2,...,x_n\}$ is a subset of
 the language of the grammar, then the answer is surely $O(1)$, since, ignoring a few edge cases, the grammar $\Sigma^*$ will be minimal for the job. So you mean
 that the language of the grammar is exactly $\{x_1,x_2,...,x_n\}$?
Martin Berger
<np-hardness><approximation-hardness><context-free>
Finding a minimal context free grammar that recognizes a finite set of strings of bounded length
Phylliida
# Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

(Asked by: username_0 on 2016-03-28)

Problem:

Given a finite set of strings $\{x\_1, x\_2, ..., x\_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a\_1, a\_2, ..., a\_k\}$, find the minimal context free grammar that recognizes all of these strings.

If $k$ is a constant, and $n = poly(\ell)$, what can one say about this problem's complexity as $\ell$ grows?

This seems similar to the [smallest grammar problem](https://en.wikipedia.org/wiki/Smallest_grammar_problem), which is NP-Hard for the optimization problem. However it is a little different because of having multiple strings, since now one needs to recognize each string independently instead of recognizing all of them at once. The smallest grammar problem is clearly a subset of this, but for small $\ell$ this might be much easier to solve, I'm not sure.

Is there a way to approximately solve this problem efficiently?

**Tags:** np-hardness, approximation-hardness, context-free

> **Comments:**
> **username_1**: Almost certainly not what you're looking for, but have you seen the [Sequitur](https://en.wikipedia.org/wiki/Sequitur_algorithm) algorithm?  It's a heuristic for a related problem.  
> **username_0**: Oo that is really close/useful for my purposes. You're right it doesn't solve this problem but thanks for the reference.  
> **username_2**: How do you measure the size of a CFG? There are lots of different measures, including total number of occurrences of variables and terminals on both sides of all productions in the grammar; number of variable occurrences on both sides of all productions; number of productions; number of distinct variables. (I doubt it will make a great difference to the asymptotic complexity)  
> **username_2**: What do you mean by grammar the *"recognizes all of these strings"*? If you mean that $\{x_1,x_2,...,x_n\}$ is a subset of  the language of the grammar, then the answer is surely $O(1)$, since, ignoring a few edge cases, the grammar $\Sigma^*$ will be minimal for the job. So you mean  that the language of the grammar is exactly $\{x_1,x_2,...,x_n\}$?  

---

## 3 answers

### Answer by username_3 on 2023-11-18. Score: 6

The following inapproximability result is known (Theorem 17 in Gruber/Holzer/Wolfsteiner, DLT 2018):

Given a context-free grammar of size $s$ generating a finite
language $L$, it is impossible to approximate the minimum grammar size of $L$ within a factor of $o(s^\frac{1}{7})$, unless P = NP.

username_3, Markus Holzer, and Simon Wolfsteiner. [On Minimal Grammar Problems for Finite Languages.](http://www.hermann-gruber.com/data/dlt-18-revised.pdf) In Mizuho Hoshi and Shinnosuke Seki, editors, 22nd International Conference on Developments in Language Theory (DLT 2018), Tokyo, Japan, volume 11088 of Lecture Notes in Computer Science, pages 342--353. Springer, September 2018.

Notice that the number of words in the reduction is exponential in their length. To my knowledge, there are no research papers that address the exact case of polynomially many words.
But the theorem shows the important point, in that it disproves the intuition that there may be a "quantity discount" effect if we want one minimal grammar for many words.

(A late answer; I hope it will still prove useful for somebody.)


---

### Answer by username_1 on 2016-03-28. Score: 4

If $\ell$ and $k$ are fixed, there are only finitely many possible problem instances, so you can write a program that has a hardcoded table of all possible instances and their solutions. Consequently, the complexity will be $O(1)$, if you consider $\ell$ and $k$ as fixed and look at the asymptotics as $n$ increases.

Why are there only finitely many possible problem instances? Because when $\Sigma$ and $\ell$ are fixed and $\Sigma$ is finite, there are only finitely many subsets of $\Sigma^1 \cup \Sigma^2 \cup \Sigma^3 \cup \cdots \cup \Sigma^{\ell}$.

> **Comments:**
> **username_0**: While you are technically correct, isn't this lookup table massive for any reasonable $\ell$ and $k$?  Specifically, you have $\sum_{i=1}^\ell k^i=(k (k^\ell-1))/(k-1)$ possible strings, and thus $2^{\sum_{i=1}^\ell k^i}$ possible problem instances.  It's my fault for not specifying that I would like a reasonable dependence on $\ell$ and $k$, but I figured a solution should be fairly reasonable for small $\ell$ and $k$ (say less than 15), yet your lookup table for $\ell=3$ and $k=3$ has 549,755,813,888 possible elements.  

---

### Answer by username_4 on 2016-03-28. Score: 2

Worst case you have a Kolmogorov complexity issue where you have chosen half of the $k^l$ words at random. Since it is random your CFG has to take $O(k^l)$ space since it cannot compress.

> **Comments:**
> **username_1**: Your answer is talking about the size of the smallest CFG.  The question seems to be asking about the running time of an algorithm to find the smallest CFG.  Therefore, while it's a valid comment, it doesn't seem to answer the question that was asked.  

---

