# Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

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, 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?

• Almost certainly not what you're looking for, but have you seen the Sequitur algorithm? It's a heuristic for a related problem.
– D.W.
Mar 29, 2016 at 8:58
• Oo that is really close/useful for my purposes. You're right it doesn't solve this problem but thanks for the reference. Mar 29, 2016 at 15:22

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}$.
• 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. Mar 28, 2016 at 19:59
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.