I have a statement I am trying to prove, and I'm very close, but I think I'm missing a couple of key concepts about regular and context-free languages.

Question: Let $ A = \{ ww \ | \ w \ \epsilon \ \Sigma^{*} \} $.

Show that any language $L$ is Turing-decidable if and only if $L$ is many-one reducible to $A$.

Where I am so far:

  1. Language $A$ is not context-free, but the complement of $A$ is context-free.

  2. Both $A$ and the complement of $A$ are decidable.

So, that means I can prove one direction of the iff statement fairly easily:

If $L$ is many-one reducible to $A$ then since $A$ is decidable from statement (2) above, also $L$ is decidable.

The other direction is giving me problems. This is all I have gleaned so far:

If $L$ is Turing-decidable, then $L$ is a regular language.

Is there some relation between regular and context-free languages with respect to reductions that I am missing? Or should I be making a different logic jump in this part of the proof?


2 Answers 2


There is a more general theorem which says that if $A$ is a decidable language and $B$ is a decidable language that is not trivial (in the sense that $B\ne\Sigma^*$ and $B\ne\emptyset\, $), then $A\le_m B$. Roughly speaking, this says that all non-trivial decidable languages are many-to-one reducible to each other, meaning that $\le_m$ is too coarse a metric to distinguish between decidable languges.

In your problem, suppose that $L\subseteq \Gamma^*$ and define a mapping $f:\Gamma^*\rightarrow\Sigma^*$ defined by: $$ f(x) = \begin{cases} \mathtt{aa} & \text{if $x\in L$}\\ \mathtt{a} & \text{if $x\notin L$} \end{cases} $$ for some $\mathtt{a}\in\Sigma^*$. This is a total computable function (since by definition, we can use the computable decider program to determine $x$'s membership in $L\, $) and it's easy to verify that $x\in L$ iff $f(x)\in A$, which is all you need to show $L\le_m A$. As Yuval noted, you don't need any results about regular or context-free languages to answer this question.


First of all, not every decidable language is regular. For example, $A$ is decidable but not regular.

Here is a hint: this question doesn't have anything to do with either regular languages or context-free languages. While we certainly need $A$ to be decidable, for the other direction we only need some really simple properties of $A$. Try to think for which $A$ it is not true that if $L$ is decidable then $L$ can be many-one reduced to $A$.

  • $\begingroup$ I'm confused, in the direction "if L is decidable...", there isn't any connection from L to A. How can A have any affect on whether or not L is decidable? $\endgroup$ Commented Feb 7, 2014 at 1:30
  • $\begingroup$ Why should it have any effect? My question was for which languages $A$ the following statement holds: If $L$ is decidable then it is many-one reducible to $A$. (If, not iff!) $\endgroup$ Commented Feb 7, 2014 at 1:38
  • $\begingroup$ Well, L must be "easier" than A since it's L <= A, so A could be decidable or undecidable, really $\endgroup$ Commented Feb 7, 2014 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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