Algorithm to find a minimal regular language containing given context-free language I am not sure that the problem is in general solvable, but here's an example of what I mean:

Any context-free language has a trivial regular language that contains it: $\Sigma^*$.
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

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



&quot;smallest&quot; 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 &quot;smaller&quot; could be &quot;having least states&quot;?
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.
There is no "smallest" regular language containing any non-regular langauge.

First, note that every finite language is regular, so any non-regular language&nbsp;$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&nbsp;$R$ and a strict superset of&nbsp;$L$.

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