Algorithm to find a minimal regular language containing given context-free language

Question

I am not sure that the problem is in general solvable, but here's an example of what I mean:

1. Any context-free language has a trivial regular language that contains it: $\Sigma^*$.
2. The language $L_1=\{a^nb^n\;|\;n\geq 0\}$ is contained in $L_2=\{a^nb^m\;|\;n,m\geq 0\}$, which is obviously a subset of $\Sigma^*$.

Questions

1. Is there a way to prove $L_2$ is the "smallest"* language which contains $L_1$?
2. Is there an algorithm for finding such language pairs given the context-free one?

---

• "smallest" means that there is no other language which also satisfies the requirement and is its proper subset.

PS

Sorry, I now realized that I cannot actually find the minimal language with the requirement given above, for example: $L_3=\{ab, aabb\} \cup \{a^nb^m\;|\; n,m \geq 2\}$ would be smaller than $L_2$, and one could continue constructing languages like that ad infinitum. So, maybe an alternative definition for "smaller" could be "having least states"?

I'm sorry for indecisiveness. Please feel free to put this on hold until I figure out the good requirement. Or suggest one yourself, if you feel like there may be an interesting one.

• J.-E. Pin: Well, $\Sigma^*$ only has one state...
• J.-E. Pin: You may find relevant references by googling "Regular Approximation of Context-Free Languages".
• wvxvw: @J.-E.Pin yes, basically I was after approximation of context-free languages, just didn't phrase it that way, thanks for the hint. I'll need to read more about it to figure out what the "smallest" requirement can be like.
• Daniel Martin: You could change the problem to "smallest language $L$ such that anything smaller differs from $L$ by only finitely many strings"

Answer 1

There is no "smallest" regular language containing any non-regular langauge.

First, note that every finite language is regular, so any non-regular language $L$ must be infinite. Consider some regular language $R\supset L$. $R\setminus L$ must also be infinite since, if it were finite, then $L = R\setminus (R\setminus L)$ would be regular, because regular languages are closed under difference. So, in particular, we can take any finite $S\subset R\setminus L$ and the langauge $R\setminus S$ is regular, is a strict subset of $R$ and a strict superset of $L$.

In other words, whenever you have a non-regular $L$ and a regular $R$ such that $L\subset R,ドル there is another regular $R'$ such that $L\subset R'\subset R$ (and, in fact, infinitely many of them).

• Anton Trunov: I think it should be "if $R \setminus L$ were finite" instead of "if $L \setminus R$ were finite".