Register

GO Classes DPP | GATE CS | Theory of Computation | Decidability

• edited by
68 views
0 0 votes

Which of these statements are true for all choices of TM $M$, string $w$, and language $L$?

  1. If $M$ recognizes $L$ and $M$ rejects $w$, then $w\notin L$.
     
  2. If $M$ recognizes $L$ and $w\notin L$, then $M$ rejects $w$.
     
  3. If $M$ loops on $w$ and $w\in L$, then $M$ does not recognize $L$.
     
  4. If $M$ loops on $w$ and $w\in L$, then $L$ is not recognizable.

1 Answer

0 0 votes

A recognizer $M$ for $L$ satisfies

$w\in L\iff M\ \mathrm{accepts}\ w$.

A is true. If $M$ rejects $w$, it did not accept $w$. 

$\therefore w\notin L$

B is false. For a nonmember, a recognizer is allowed to either $\boxed{\mathrm{reject}}$ or $\boxed{\mathrm{loop\ forever}}$.

So $w\notin L$ does not force rejection.

C is true. If $w\in L$, a recognizer for $L$ must eventually accept $w$. If $M$ loops on that member, $M$ cannot be a recognizer for $L$.

D is false. It only proves that this particular machine $M$ does not recognize $L$. Some other TM could still recognize $L$.

Voting & Accepting an answer helps improve the community
Answer:
← Previous · MADE EASY TEST SERIE...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

1 1 vote
1 1 answer
84
84 views
GO Classes asked Sep 30
84 views
GO Classes DPP | GATE CS | Theory of Computation | Decidability
Which of the following languages are recognizable?$\{\langle M\rangle\mid M\ \mathrm{is\ a\ TM\ and}\ L(M)\ \mathrm{is\ finite}\}$ $\{\langle M_1,M_2,w\rangle\mid M_1\ \m...
0 0 votes
1 1 answer
69
69 views
GO Classes asked Sep 30
69 views
GO Classes DPP | GATE CS | Theory of Computation | Decidability
Define, $A_{\mathrm{TM}}=\{\langle M,w\rangle\mid M\ \mathrm{is\ a\ TM\ and}\ w\in L(M)\}$.Consider the TM $N$:On input $\langle M,w\rangle$:Simulate $M$ on $w$. If $M$ a...
0 0 votes
1 1 answer
67
67 views
GO Classes asked Sep 30
67 views
GO Classes DPP | GATE CS | Theory of Computation | Recognizable
Which of the following languages are Turing-recognizable?$\{\langle M\rangle\mid M\ \mathrm{is\ a\ deterministic\ TM\ and}\ M\ \mathrm{accepts}\ 010\}$ $\{\langle M\rangl...
0 0 votes
1 1 answer
60
60 views
GO Classes asked Sep 30
60 views
GO Classes DPP | GATE CS | Theory of Computation | Decidability
Which of these statements are true for all choices of TM $M$, string $w$, and language $L$?If $M$ decides $L$ and $M$ rejects $w$, then $w\notin L$. If $M$ decides $L$ an...