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?
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}$.