Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Materials:
Decidability Problems for Grammars
Some Reduction Inferences
Example reductions
Recent questions tagged decidability
0
votes
0
answers
1
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
+
–
4
votes
0
answers
2
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
560
views
GO Classes
asked
Feb 5
Theory of Computation
goclasses2024-mockgate-14
theory-of-computation
decidability
multiple-selects
2-marks
+
–
3
votes
1
answer
3
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
542
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
4
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
222
views
amitarp818
asked
Dec 28, 2023
Theory of Computation
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
5
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
+
–
0
votes
1
answer
6
#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
340
views
amit166
asked
Jan 28, 2023
Theory of Computation
decidability
+
–
1
votes
0
answers
7
DRDO CSE 2022 Paper 2 | Question: 12 (a)
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} \cup 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
283
views
admin
asked
Dec 15, 2022
Theory of Computation
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
+
–
2
votes
0
answers
8
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
9
DRDO CSE 2022 Paper 2 | Question: 12 (b)
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=\left\{a \circ b \mid a \in L_{1}, b \in L_{2}\right\}$ where $a$ o $b$ denotes the concatenation of the strings $a$ and $b$
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
186
views
admin
asked
Dec 15, 2022
Theory of Computation
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
+
–
1
votes
0
answers
10
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
262
views
admin
asked
Dec 15, 2022
Theory of Computation
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
+
–
1
votes
2
answers
11
toc decidablity
M is a Turing Machine and M is the only Turing Machine that accepts L(M) is decidable. TRUE/FALSE
M is a Turing Machine and M is the only Turing Machine that accepts L(M) is decidable. TRUE/FALSE
jugnu1337
622
views
jugnu1337
asked
Nov 7, 2022
Theory of Computation
theory-of-computation
decidability
true-false
+
–
4
votes
1
answer
12
GO Classes Test Series 2023 | Theory of Computation | Test 5 | Question: 4
Consider the following languages : $\mathrm{L} 1:=\{\langle \text{M}\rangle \mid \text{M}$ is a $\text{TM},$ and $\text{M}$ is the only $\text{TM}$ that accepts $\mathrm{L}(\mathrm{M})\}.$ ... and $|\text{M}|<1000\} .$ Which of the above languages is Decidable? Only $\text{L1}$ Only $\text{L2}$ Both None
Consider the following languages :$\mathrm{L} 1:=\{\langle \text{M}\rangle \mid \text{M}$ is a $\text{TM},$ and $\text{M}$ is the only $\text{TM}$ that accepts $\mathrm{L...
GO Classes
600
views
GO Classes
asked
Aug 1, 2022
Theory of Computation
goclasses2024-toc-5-weekly-quiz
goclasses
theory-of-computation
turing-machine
decidability
1-mark
+
–
1
votes
1
answer
13
Igate Test Series
please explain all options with example
please explain all options with example
SKMAKM
564
views
SKMAKM
asked
Jul 20, 2022
Theory of Computation
decidability
closure-property
+
–
0
votes
1
answer
14
MADE EASY 2022 Work book -Theory of Computation series
Let L be a regular language on alphabet Σ. The union of the myhill-nerode equivalence classes is always _____, and the pairwise intersection of the myhill-nerode equivalence classes is always Fill up the blanks
Let L be a regular language on alphabet Σ. The union of the myhill-nerode equivalence classes is always _____, and the pairwise intersection of the myhill-nerode equival...
abhinowKatore
392
views
abhinowKatore
asked
Mar 7, 2022
Theory of Computation
theory-of-computation
regular-languages
finite-automata
minimal-state-automata
decidability
+
–
12
votes
2
answers
15
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.8k
views
Arjun
asked
Feb 15, 2022
Theory of Computation
gatecse-2022
theory-of-computation
turing-machine
decidability
multiple-selects
2-marks
+
–
Page:
1
2
3
4
5
6
...
16
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register