patternMinor
Algorithm to find a minimal regular language containing given context-free language
Viewed 0 times
containingfreeregularlanguagealgorithmcontextfindminimalgiven
Problem
I am not sure that the problem is in general solvable, but here's an example of what I mean:
Questions
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.
- 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 "smallest"* language which contains $L_1$?
- 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.
Solution
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).
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).
Context
StackExchange Computer Science Q#50938, answer score: 3
Revisions (0)
No revisions yet.