I cannot for the life of me wrap my head around these reductions.

Specifically, the example I'm wrestling with:

REGULAR = {<M> | M is a Turing Machine and L(M) is regular}

Reduction to ACCEPT_TM where ACCEPT_TM = {<M,w> | M is a TM and w is a string, M accepts w}

Construct TM M':
M' = "On input x
    1. If x has the form 0^n1^n, accept
    2. Otherwise, run M on input w and accept if M accepts w."

If M accepts w, M' accepts SIGMA*
If M does not accept w, M' accepts 0^n1^n

I understand the first implication (if M accepts w, M' accepts SIGMA*).

What I don't understand is the implication that if M does not accept w, then M' accepts strings of the form 0^n1^n. How are they reaching this conclusion? To me, it seems like "If x is in the form 0^n1^n, then don't run M", which doesn't seem logically equivalent.

  • $\begingroup$ this smells like a homework problem. @Phil, could you please explain the source of this question ? Our current site policy is NOT to answer homework questions, even if clearly labelled as such. Please see this discussion: meta.cstheory.stackexchange.com/questions/209/… $\endgroup$ – Suresh Venkat Nov 1 '10 at 22:27
  • $\begingroup$ I suppose we'd have to define homework. I'm not asking for anything other than a further explanation on a completed proof, one that is standard in many textbooks (Sipser). If "homework" is that work which a student is assigned to complete individually, this is not homework. However, I suppose if anything taught/learned in an educational setting is considered homework, then yes, this is homework. If you could clarify what is allowed/prohibited, I'd appreciate it and gladly follow the rules. Thanks. Also, the reason I brought this question here is because I was referred via SO with a HW tag $\endgroup$ – prelic Nov 1 '10 at 22:36

If M does not accept w, then the only case in which M' accepts is if its input is of the form 0^n 1^n.

  • $\begingroup$ Thank you. My only other question then is why do we want to recognize a non-regular language if M does not accept w? Basically, my question is why don't we give M' the opportunity to reject? Shouldn't we be [explicitly] rejecting on non-regular inputs? $\endgroup$ – prelic Nov 1 '10 at 22:19
  • $\begingroup$ They show "M' accepts a regular language" <=> "M accepts w". This means that if you want to decide the latter, it's enough if you decide the former. This is what a reduction is all about. $\endgroup$ – Dana Moshkovitz Nov 2 '10 at 1:18

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.