[Solved]: Proving iff statement with reductions

Problem Detail: 

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?

Asked By : Alex Chumbley

Answered By : Rick Decker

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21405

 Ask a Question

 Download Related Notes/Documents