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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Well, $\Sigma^*$ only has one state... $\endgroup$
    – J.-E. Pin
    Dec 19, 2015 at 13:30
  • 6
    $\begingroup$ You may find relevant references by googling "Regular Approximation of Context-Free Languages". $\endgroup$
    – J.-E. Pin
    Dec 19, 2015 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, 2015 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, 2016 at 17:13

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
1
  • $\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, 2015 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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