Register

Materials:

Recent questions tagged decidability

0 0 votes
1 1 answer
45
45 views
GO Classes DPP | GATE CS | Theory of Computation | Recognizable vs Decidable Closure
Select all the true statements.Recognizable languages are closed under complement. Decidable languages are closed under complement. Recognizable languages are closed unde...
User Avatar
0 0 votes
1 1 answer
49
49 views
GO Classes DPP | GATE CS | Theory of Computation | Decidability
Consider the following problems. Which of the following is decidable?Given two Turing machines $M$ and $N$, determine whether the encoded descriptions of $M$ and $N$ are ...
User Avatar
0 0 votes
1 1 answer
61
61 views
GO Classes DPP | GATE CS | Theory of Computation | Decidability
Determine whether the following assertion is correct:"If a language $L$ and its complement $\overline{L}$ are both Turing-recognizable, then $L$ is decidable. "Enter $1$ ...
User Avatar
0 0 votes
1 1 answer
80
80 views
GO Classes DPP | GATE CS | Theory of Computation | Turing Machine
Consider, $A_{\mathrm{TM}}=\{\langle M,w\rangle\mid M\ \mathrm{is\ a\ TM\ and}\ M\ \mathrm{accepts}\ w\}$Mark all properties that are certainly true for the stated langua...
User Avatar
0 0 votes
1 1 answer
52
52 views
GO Classes DPP | GATE CS | Theory of Computation | Halting Undecidability
Which statement is INCORRECT?A universal Turing machine can simulate any Turing machine $M$ on any input for $M$. The Church Thesis states that the informal notion of an ...
User Avatar
1 1 vote
1 1 answer
60
60 views
GO Classes DPP | GATE CS | Theory of Computation | Decidability
Suppose a language $L$ is Turing-decidable. Which statement must be true?For a string $s\notin L$, a Turing machine deciding $L$ will eventually enter a reject state. For...
User Avatar
1 1 vote
1 1 answer
97
97 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...
User Avatar
0 0 votes
1 1 answer
80
80 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...
User Avatar
0 0 votes
1 1 answer
69
69 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...
User Avatar
0 0 votes
1 1 answer
78
78 views
GO Classes DPP | GATE CS | Theory of Computation | Decidability
Given an NFA $N$, we want to decide efficiently whether $$L(N)\cap 0^*=\varnothing$$ Which method is appropriate?Convert $N$ to a DFA, take a product with a DFA for $0^*$...
User Avatar
0 0 votes
1 1 answer
68
68 views
GO Classes DPP | GATE CS | Theory of Computation | Decidability
Let, $A_{\mathrm{DFA}}=\{\langle D,w\rangle\mid D\ \mathrm{accepts}\ w\}$,$E_{\mathrm{DFA}}=\{\langle D\rangle\mid L(D)=\varnothing\}$,and$EQ_{\mathrm{DFA}}=\{\langle D_1...
User Avatar
0 0 votes
1 1 answer
61
61 views
GO Classes DPP | GATE CS | Theory of Computation | DFA vs Turing
Consider the following statements:If a DFA can decide membership in a language $L$, then some Turing machine can also decide membership in $L$. If a Turing machine can de...
User Avatar
0 0 votes
1 1 answer
50
50 views
GO Classes DPP | GATE CS | Theory of Computation | Recognizable
Is the intersection of an arbitrary Turing-recognizable language and an arbitrary co-Turing-recognizable language necessarily decidable?Yes, because of the containment di...
User Avatar
0 0 votes
1 1 answer
53
53 views
GO Classes DPP | GATE CS | Theory of Computation | Decidable vs Recognizable
Which of the following correctly describes the relationship between decidable and Turing-recognizable languages?Decidable languages are a subset of Turing-recognizable la...
User Avatar
0 0 votes
0 0 answers
112
112 views
Which of the following are decidable?
Which of the following are decidable? 1) Whether a given grammar is context-free?2) Whether a given grammar is rec ?3) Whether a given grammar is recursively enumerable ...
User Avatar
Page: