# Question about Mapping Reductions (Clarify Example)

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.

• 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/… – Suresh Venkat Nov 1 '10 at 22:27
• 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 – prelic Nov 1 '10 at 22:36