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?
Finding a minimal context free grammar that recognizes a finite set of strings of bounded length
np hardness;approximation hardness;context free