Register

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 61

• retagged by
656 views
3 votes
3 votes
Which of the following is/are undecidable?
  1. $L=\left\{\langle M\rangle \mid M\right.$ is a TM, $\mathrm{L}(M) \neq \emptyset$, and $\left.\mathrm{L}(M) \neq \Sigma^*\right\}$.
  2. $\{\langle M\rangle \mid M$ is a TM and $\mathrm{L}(M)=\varnothing\}$
  3. $\mathrm{L}=\{\langle\mathrm{M}>| \mathrm{M}$ is a TM and $\mathrm{L}(\mathrm{M})$ is uncountable $\}$
  4. $L=\{\langle M\rangle \mid M$ is a DFA and $L(M)$ is uncountable $\}$
• retagged by
User Avatar

1 Answer

3 votes
3 votes
EVERY language is countable. So, Option C $\&$ D are trivial properties (trivially false), hence countable.
• edited by
1 flag:
✌ Edit necessary (rajan31 “"hence decidable"”)
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

627
views
1 answers
4 votes
GO Classes asked Jan 13
627 views
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 64
Which of the following statements about Turing machines is false?For every context-sensitive language $L$, there is a Turing machine that accepts precisely the ... behaviour of any given Turing machine $B$ on any given finite input.
User Avatar
608
views
1 answers
5 votes
GO Classes asked Jan 13
608 views
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 36
Consider the system $A \mathbf{x}=\mathbf{b}$, with coefficient matrix $A$ and augmented matrix $[A \mid b]$. The sizes of $\mathbf{b}, A$ ... exists) if and only if $\operatorname{rank}[A]>$ $\operatorname{rank}[A \mid b]$.
User Avatar
754
views
1 answers
9 votes
GO Classes asked Jan 13
754 views
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 38
A binary relation $\mathrm{R}$ over a set $\mathrm{A}$ is called a "GO Relation" if for all $\mathrm{x}, \mathrm{y}, \mathrm{z}$ $\in A$ ... relation then $R$ is reflexive.If $R$ is an equivalence relation then $R$ is a GO relation.
User Avatar
930
views
1 answers
8 votes
GO Classes asked Jan 13
930 views
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 41
A self-dual logic function is a function that is identical to its dual. An anti-self-dual logic function is a function whose dual is the same as the complement of the function.A ... .
User Avatar
Link Copied!