If a language is m-reducible to a regular language, does it mean that this language is also necessarily a regular language?

Question

I've been going back and forth with this for a dew days, can't quite be sure.

When I look at the pumping lemma method, I think a context-free language could possibly be reduced to a regular language.

Answer 1

The answer to your question is no. There's a general result you can use in this case:

Theorem. If $A$ and $B$ are any decidable languages and $B\ne\varnothing$ and $B\ne\Sigma^*$, then $A\le_\text{M} B$.

This says that any nontrivial decidable languages are mapping reducible to each other. In other words, mapping reducibility tells you nothing about decidable languages.

Here's an example. Let $L=\{0^n1^n\mid n\ge 0\}$. This is a well-known non-regular language. Now let $R$ be, say the regular language $\{0\}$. Then $L\le_\text{M} R$ by the mapping $f:\{0, 1\}^*\rightarrow\{0, 1\}^*$ defined by $$ f(s) = \begin{cases} 0\quad\text{if $s=0^n1^n$ for some $n\ge 0$}\\ 1\quad\text{otherwise} \end{cases} $$ It's obvious that $f$ is Turing-computable and that $s\in \{0^n1^n\} \Longleftrightarrow f(s)\in R$, which is exactly what you need to show that this non-regular language is mapping reducible to this regular language.