Register

GATE CSE 2026 | Set 2 | Theory of Computation| Memory Based | Question 30

413 views
2 2 votes

Which of the following statements is exactly equivalent to the given statement $:$ 

"$\text{TM M decides the language L} \subseteq\{0,1\}$"

  1. $\mathrm{M}$ accepts all input strings in $\mathrm{L}$
     
  2. $\mathrm{M}$ halts on all input strings in $\{0,1\}^*$
     
  3. $\mathrm{M}$ accepts all input strings in $\mathrm{L}$ & rejects all input strings in $\{0,1\}^*-\mathrm{L}$.
     
  4. $\mathrm{M}$ rejects all input strings in $\{0,1\}^*-\mathrm{L}$

1 Answer

0 0 votes
It's given that M decides L which means two things must happen-

1)M halts on it, no looping forever

2)M gives the correct answer i.e accepts if the string is in L, reject if it isn't

Option C exactly describes this- M accepts every string in L and reject all input strings in {0,1}* - L (the complement of L)
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2026 | Set ...Next → · GATE CSE 2026 | Set ...
← Previous in category · GATE CSE 2026 | Set ...Next in category → · GATE CSE 2026 | Set ...
Position:
Show:

Related questions

1 1 vote
0 0 answers
456
456 views
GO Classes asked Feb 11
456 views
GATE CSE 2026 | Set 2 | Theory of Computation| Memory Based | Question 31
Consider the following finite automaton $\mathrm{D}_1$ and $\mathrm{D}_2:$ $\mathrm{L}\left(\mathrm{D}_1\right) \cap \mathrm{L}\left(\mathrm{D}_2\right)=\{\epsilon\}$ $\l...
2 2 votes
1 1 answer
383
383 views
GO Classes asked Feb 11
383 views
GATE CSE 2026 | Set 2 | Theory of Computation| Memory Based | Question 29
$L=\left\{a^i ~b^j ~c^k ~d^l \mid i, j, k, l \geq 1\right\}$Which of the following conditions ensures $L$ is $\text{CFL}$?$i+j=k+l$ $i=k$ and $j=l$ $i+k=j+l$ $i=l$ and $j...
6 6 votes
3 3 answers
2.0k
2.0k views
GO Classes asked Feb 13
1,997 views
GATE CSE 2026 | Set 2 | Computer Network | Memory Based | Question 65
Given that Maximum Segment size is $2 ~\mathrm{KB}$ and the slow start threshold (ssthresh) is $16 ~\mathrm{KB}$, how many transmission round is required to reach in cong...
3 3 votes
0 0 answers
618
618 views
GO Classes asked Feb 13
618 views
GATE CSE 2026 | Set 2 | Computer Network | Memory Based | Question 64
A link layer protocol is designed which has assigned a sequence number to every byte of data transmitted over a point-to-point link. The link length is $3000\,\text{km}$,...