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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.