Can you reduce every decidable language to a regular language?

Question

One of my previous questions on an exam was the following

Can you reduce a decidable language to a given regular language? (decidable language $\leq _m$ regular language). If so, does this mean that you can reduce every CFL to a regular language?

The reductions are all referring to many-one reductions. My intuition tells me that this is possible as all regular languages are also decidable.

Answer 1

In fact, every non-trivial language is $\text{R}$-hard. That is, every decidable language is reducible to every non-trivial language. Indeed, let $A$ be a decidable language, and let $B$ be a non-trivial language. A reduction from $A$ to $B$ operates as follows. On input $x$, check whether $x\in A$ (this can be done as $A$ is decidable), then:

• if $x \in A$, the reduction outputs $y_{in}$
• if $x\notin A$, the reduction outputs $y_{out}$

where $y_{in}$ and $y_{out}$ are constant words in $B$ and $\overline{B}$, respectively.