Question about mapping reducibility I am working on an assignment where one of the sub questions is:


  Let $A$ and $B$ be languages. Suppose $A$ is context free and $A ≤_m B$, which means that there is a computable function $f\colon \Sigma^* \to \Sigma^*$ such that for all $w \in \Sigma^*$, $w \in A$ iff $f(w) \in B$. Is it possible that $B$ is regular?


My take on this is that since context-free languages are on a 'higher' level than regular languages this is not possible. Apparently this is not the case, but I do not understand why.
Does anyone have a good explanation?
If $A$ is computable and $B$ is any nontrivial language (that is, $B \neq \emptyset,\Sigma^*$) then $A \leq_m B$. Indeed, pick $x \in B$ and $y \notin B$, and construct a computable reduction which decides whether its input is in $A$ or not, and outputs $x$ or $y$ accordingly.

Another issue you seem to be confused about is the meaning of context-free. The fact that a language is context-free doesn't preclude it from being regular. On the contrary, all regular languages are context-free.