Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
A very minor nit. Instead of \epsilon in your question, use \in to indicate set membership. –  Rick Decker Feb 7 at 3:44
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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$.

share|improve this answer
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? –  Alex Chumbley Feb 7 at 1:30
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!) –  Yuval Filmus Feb 7 at 1:38
Well, L must be "easier" than A since it's L <= A, so A could be decidable or undecidable, really –  Alex Chumbley Feb 7 at 1:43
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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