Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for decidability
43
votes
7
answers
1
GATE CSE 2012 | Question: 24
Which of the following problems are decidable? Does a given program ever produce an output? If $L$ is a context-free language, then, is $\bar{L}$ also context-free? If $L$ is a regular language, then, is $\bar{L}$ also regular? If $L$ is a recursive language, then, is $\bar{L}$ also recursive? $1, 2, 3, 4$ $1, 2$ $2, 3, 4$ $3, 4$
Which of the following problems are decidable?Does a given program ever produce an output?If $L$ is a context-free language, then, is $\bar{L}$ also context-free?If $L$ i...
Arjun
15.5k
views
Arjun
asked
Sep 25, 2014
Theory of Computation
gatecse-2012
theory-of-computation
decidability
normal
+
–
86
votes
4
answers
2
GATE CSE 2017 Set 1 | Question: 39
Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if there exists a Turing machine $M$ which given an ... $L_{f}$ is recursive, but not conversely. If $f$ is computable then $L_{f}$ is recursively enumerable, but not conversely.
Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if th...
Arjun
18.3k
views
Arjun
asked
Feb 14, 2017
Theory of Computation
gatecse-2017-set1
theory-of-computation
decidability
difficult
+
–
31
votes
7
answers
3
GATE CSE 2020 | Question: 26
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M.$L_1 = \{\left \langle M \right \r...
Arjun
14.3k
views
Arjun
asked
Feb 12, 2020
Theory of Computation
gatecse-2020
theory-of-computation
decidability
2-marks
+
–
12
votes
2
answers
4
GATE CSE 2022 | Question: 36
Which of the following is/are undecidable? Given two Turing machines $\textit{M}_{1}$ and $\textit{M}_{2},$ decide if $\textit{L(M}_{1}) = \textit{L(M}_{2}).$ Given a Turing machine $\textit{M},$ decide if $\textit{L(M)}$ is ... $\textit{M},$ decide if $\textit{M}$ takes more than $1073$ steps on every string.
Which of the following is/are undecidable?Given two Turing machines $\textit{M}_{1}$ and $\textit{M}_{2},$ decide if $\textit{L(M}_{1}) = \textit{L(M}_{2}).$Given a Turin...
Arjun
9.9k
views
Arjun
asked
Feb 15, 2022
Theory of Computation
gatecse-2022
theory-of-computation
turing-machine
decidability
multiple-selects
2-marks
+
–
32
votes
1
answer
5
GATE CSE 2021 Set 2 | Question: 36
Consider the following two statements about regular languages: $S_1$: Every infinite regular language contains an undecidable language as a subset. $S_2$: Every finite language is regular. Which one of the following choices is correct? Only $S_1$ is true Only $S_2$ is true Both $S_1$ and $S_2$ are true Neither $S_1$ nor $S_2$ is true
Consider the following two statements about regular languages:$S_1$: Every infinite regular language contains an undecidable language as a subset.$S_2$:...
Arjun
11.9k
views
Arjun
asked
Feb 18, 2021
Theory of Computation
gatecse-2021-set2
theory-of-computation
regular-language
decidability
2-marks
+
–
4
votes
0
answers
6
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 65
Which of the following statements are true for every language $\mathrm{L} \subseteq\{0,1\}^*?$ $L^{\star}$ is infinite. $L$ is accepted by some DFA if and only if $L$ is accepted by some NFA. If $\mathrm{L}$ is the ... $\mathrm{L}$ is undecidable. If $\mathrm{L}$ is the union of two decidable languages, then $\mathrm{L}$ is decidable.
Which of the following statements are true for every language $\mathrm{L} \subseteq\{0,1\}^*?$$L^{\star}$ is infinite.$L$ is accepted by some DFA if and only if $L$ is ac...
GO Classes
561
views
GO Classes
asked
Feb 5
Theory of Computation
goclasses2024-mockgate-14
theory-of-computation
decidability
multiple-selects
2-marks
+
–
0
votes
0
answers
7
Hopcroft, Ullman Theorem 9.7 Reductions
There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself as input. It is known and proved that Ld is a non- ... and Ld is non-RE, ATM must be non-RE. But we know that ATM is Recursively Enumerable and undecidable. How is this possible?
There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself a...
dopq12
71
views
dopq12
asked
Mar 5
Theory of Computation
decidability
theory-of-computation
turing-machine
reduction
recursive-and-recursively-enumerable-languages
+
–
3
votes
1
answer
8
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 61
Which of the following is/are undecidable? $L=\left\{\langle M\rangle \mid M\right.$ is a TM, $\mathrm{L}(M) \neq \emptyset$, and $\left.\mathrm{L}(M) \neq \Sigma^*\right\}$. $\{\langle M\rangle \mid M$ ... $\}$ $L=\{\langle M\rangle \mid M$ is a DFA and $L(M)$ is uncountable $\}$
Which of the following is/are undecidable?$L=\left\{\langle M\rangle \mid M\right.$ is a TM, $\mathrm{L}(M) \neq \emptyset$, and $\left.\mathrm{L}(M) \neq \Sigma^*\right\...
GO Classes
543
views
GO Classes
asked
Jan 13
Theory of Computation
goclasses2024-mockgate-11
goclasses
theory-of-computation
decidability
multiple-selects
2-marks
+
–
1
votes
0
answers
9
Decidability
L(M)={0} We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable) I don’t understand why this is not decidable. We can easily create a turing that accepts this language
L(M)={0}We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable)I don’t ...
amitarp818
224
views
amitarp818
asked
Dec 28, 2023
Theory of Computation
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
14
votes
5
answers
10
GATE CSE 2021 Set 1 | Question: 39
For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$ ... decidable $L_1$ is decidable and $L_2$ is undecidable $L_1$ is undecidable and $L_2$ is decidable Both $L_1$ and $L_2$ are undecidable
For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$. Consider the following two languages.$$\begin{array}{ll} L_1 = \{ \langle M \rangle \mid M \text...
Arjun
9.8k
views
Arjun
asked
Feb 18, 2021
Theory of Computation
gatecse-2021-set1
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
easy
2-marks
+
–
0
votes
0
answers
11
Undecidability Doubt
If G is a CFG then L(G) = (Sigma)* is Decidable or Undecidable? The reference where I solved this question says this is an Undecidable problem! But I think it's Decidable . Help would be appreciated.
If G is a CFG then L(G) = (Sigma)* is Decidable or Undecidable?The reference where I solved this question says this is an Undecidable problem! But I think it's Decidable ...
Sparsh-NJ
219
views
Sparsh-NJ
asked
Aug 6, 2023
Theory of Computation
theory-of-computation
decidability
+
–
38
votes
4
answers
12
GATE CSE 2015 Set 3 | Question: 53
Language $L_1$ is polynomial time reducible to language $L_2$. Language $L_3$ is polynomial time reducible to language $L_2$, which in turn polynomial time reducible to language $L_4$. Which of the following is/are true? $\text{ if } L_4 \in P, \text{ then } L_2 \in P$ ... $\text{ if } L_4 \in P, \text{ then } L_3 \in P$ II only III only I and IV only I only
Language $L_1$ is polynomial time reducible to language $L_2$. Language $L_3$ is polynomial time reducible to language $L_2$, which in turn polynomial time reducible to l...
go_editor
9.0k
views
go_editor
asked
Feb 16, 2015
Theory of Computation
gatecse-2015-set3
theory-of-computation
decidability
normal
+
–
58
votes
2
answers
13
GATE CSE 2010 | Question: 17
Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? $L_2 - L_1 \:\text{is recursively enumerable.}$ ... $L_2 \cap L_3 \:\text{is recursively enumerable.}$ $L_2 \cup L_3 \:\text{is recursively enumerable.}$
Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessar...
go_editor
16.0k
views
go_editor
asked
Sep 29, 2014
Theory of Computation
gatecse-2010
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
normal
+
–
48
votes
3
answers
14
GATE CSE 2008 | Question: 10
Which of the following are decidable? Whether the intersection of two regular languages is infinite Whether a given context-free language is regular Whether two push-down automata accept the same language Whether a given grammar is context-free I and II I and IV II and III II and IV
Which of the following are decidable?Whether the intersection of two regular languages is infiniteWhether a given context-free language is regularWhether two push-down au...
Kathleen
13.5k
views
Kathleen
asked
Sep 11, 2014
Theory of Computation
gatecse-2008
theory-of-computation
decidability
easy
+
–
32
votes
3
answers
15
GATE CSE 2001 | Question: 7
Let a decision problem $X$ be defined as follows: $X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$? You may assume that the halting problem of Turing machine is undecidable but partially decidable. Show that $X$ is undecidable Show that $X$ is not even partially decidable
Let a decision problem $X$ be defined as follows:$X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$?You may assume th...
Kathleen
4.5k
views
Kathleen
asked
Sep 14, 2014
Theory of Computation
gatecse-2001
theory-of-computation
decidability
turing-machine
easy
descriptive
+
–
0
votes
1
answer
16
#gate questions
which one true 1. Determining whether context-free grammar is un-decidable 2. Whether a given grammar is context-free is decidable
which one true1. Determining whether context-free grammar is un-decidable2. Whether a given grammar is context-free is decidable
amit166
341
views
amit166
asked
Jan 28, 2023
Theory of Computation
decidability
+
–
46
votes
2
answers
17
GATE CSE 1990 | Question: 3-vii
It is undecidable whether: An arbitrary Turing machine halts after $100$ steps. A Turing machine prints a specific letter. A Turing machine computes the products of two numbers None of the above.
It is undecidable whether:An arbitrary Turing machine halts after $100$ steps.A Turing machine prints a specific letter.A Turing machine computes the products of two numb...
makhdoom ghaya
12.5k
views
makhdoom ghaya
asked
Nov 22, 2016
Theory of Computation
gate1990
normal
theory-of-computation
decidability
multiple-selects
+
–
48
votes
7
answers
18
GATE CSE 2015 Set 2 | Question: 21
Consider the following statements. The complement of every Turing decidable language is Turing decidable There exists some language which is in NP but is not Turing decidable If L is a language in NP, L is Turing decidable Which of the above statements is/are true? Only II Only III Only I and II Only I and III
Consider the following statements.The complement of every Turing decidable language is Turing decidableThere exists some language which is in NP but is not Turing decidab...
go_editor
15.3k
views
go_editor
asked
Feb 12, 2015
Theory of Computation
gatecse-2015-set2
theory-of-computation
decidability
easy
+
–
2
votes
0
answers
19
DRDO CSE 2022 Paper 2 | Question: 13
Let $L$ be the following language. $L=\left\{P\left(x_{1}, x_{2}, \ldots, x_{n}\right) \mid P\right.$ is a polynomial with an integral root $\}$. Explain why the following Turing Machine description cannot decide the language $L$. ... $0,$ accept. Else, reject.
Let $L$ be the following language.$L=\left\{P\left(x_{1}, x_{2}, \ldots, x_{n}\right) \mid P\right.$ is a polynomial with an integral root $\}$.Explain why the following ...
admin
234
views
admin
asked
Dec 15, 2022
Theory of Computation
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
4-marks
+
–
1
votes
0
answers
20
DRDO CSE 2022 Paper 2 | Question: 12 (c)
Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turing machine for the following languages. $L_{1} \cap L_{2}$
Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turi...
admin
263
views
admin
asked
Dec 15, 2022
Theory of Computation
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
+
–
Page:
1
2
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register