# 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

## 1 Answer

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.

• 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? – prelic Nov 1 '10 at 22:19
• 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. – Dana Moshkovitz Nov 2 '10 at 1:18