<p>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.</p>

CC BY-SA 2.5
2010-11-01T22:19:11.273Z
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
CC BY-SA 2.5
2010-11-02T01:18:42.650Z
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
CC BY-SA 2.5
2010-11-01T22:05:08.603Z
2010-11-01T22:05:08.603Z
Dana Moshkovitz
<p>I cannot for the life of me wrap my head around these reductions.</p>

<p>Specifically, the example I'm wrestling with:</p>

<pre><code>REGULAR = {&lt;M&gt; | M is a Turing Machine and L(M) is regular}

Reduction to ACCEPT_TM where ACCEPT_TM = {&lt;M,w&gt; | 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
</code></pre>

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

<p>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.</p>

CC BY-SA 2.5
2010-11-01T22:27:04.490Z
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: http://meta.cstheory.stackexchange.com/questions/209/homework-or-things-that-look-like-homework
Suresh Venkat
CC BY-SA 2.5
2010-11-01T22:36:58.127Z
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
<automata-theory><turing-machines><computability><reductions>
Question about Mapping Reductions (Clarify Example)
prelic
# Question about Mapping Reductions (Clarify Example)

(Asked by: username_0 on 2010-11-01)

I cannot for the life of me wrap my head around these reductions.
Specifically, the example I'm wrestling with:
REGULAR = { | M is a Turing Machine and L(M) is regular}

Reduction to ACCEPT_TM where ACCEPT_TM = { | 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.

**Tags:** automata-theory, turing-machines, computability, reductions

> **Comments:**
> **username_1**: 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: http://meta.cstheory.stackexchange.com/questions/209/homework-or-things-that-look-like-homework  
> **username_0**: 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  

---

## 1 answers

### Answer by username_2 on 2010-11-01. Score: 3 | Accepted 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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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.  

---

