Deciding whether a subset of a regular language is regular

Question

So let's have $2$ regular languages $R_1$ and $R_2$. Then we have language $L$ where $R_1 \subseteq L \subseteq R_2$. Decide whether $L$ is always regular language or not.

So my approach was this. Let's have $$R_1=\{a^mb^l \;|\;m,l\ge0\}$$ $$L=\{a^nb^n\;|\; n \ge0\}$$ $$R_2=\{a^mb^l \;|\;m,l\ge0\}$$

So we can easily prove that $R_1,R_2$ are regular by an automaton, and we can prove that $L$ is not regular by Pumping lemma. So we have found languages for which that does not hold $\implies$ it is not always regular.

Is this correct? Or have I made mistake somewhere?

Answer 1

A quick hacky answer is that regular languages don't have to be infinite, so we just take $R_1 = \{ab, aabb\}$ and show it's a subset of both $R_2$ and $L$.

If you want a more damning answer, let $R_1$ be the set of all possible strings you can form from the characters $($ and $)$. Let $L$ be the set of all possible strings of balanced parenthesis, ie $(()(())) \in L$, $((($ and $())($ are $\notin L$. Finally, let $R_2 = \{(), ()(), ()()(), ...\}$. Can you show that $R_2$ is regular and $L$ is not?

Answer 2

Here's another way to generate a lot of solutions. $\def\x{\mathtt{x}}R_1 = (\x\x)^\ast$ and let $R_2 = \x^\ast$. Then $R_1$ and $R_2$ are obviously both regular. But there are plenty of nonregular languages $L$ with $R_1\subset L\subset R_2$. For example, let $L = R_1\cup \left\{\x^p\mid p\text{ prime}\right\}$ or $L = R_1\cup \left\{\x^{n^2}\right\}$ will work. In general, you can take any infinite irregular set $S$ of odd-length strings, and then $R_1\cup S$ has the desired property.