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:
- Language $A$ is not context-free, but the complement of $A$ is context-free.
- 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 $BneSigma^*$ and $Bneemptyset, $), then $Ale_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 $Lsubseteq Gamma^*$ and define a mapping $f:Gamma^*rightarrowSigma^*$ defined by: $$ f(x) = begin{cases} mathtt{aa} & text{if $xin L$} mathtt{a} & text{if $xnotin L$} end{cases} $$ for some $mathtt{a}inSigma^*$. 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 $xin L$ iff $f(x)in A$, which is all you need to show $Lle_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
