5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Well, $\Sigma^*$ only has one state... $\endgroup$ – J.-E. Pin Dec 19 '15 at 13:30
  • 6
    $\begingroup$ You may find relevant references by googling "Regular Approximation of Context-Free Languages". $\endgroup$ – J.-E. Pin Dec 19 '15 at 13:35
  • $\begingroup$ @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. $\endgroup$ – wvxvw Dec 19 '15 at 20:08
  • 1
    $\begingroup$ You could change the problem to "smallest language $L$ such that anything smaller differs from $L$ by only finitely many strings" $\endgroup$ – Daniel Martin Jan 14 '16 at 17:13
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I think it should be "if $R \setminus L$ were finite" instead of "if $L \setminus R$ were finite". $\endgroup$ – Anton Trunov Dec 20 '15 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.