Register

Materials:

Recent questions tagged decidability

0 votes
1 answer
184
Decidability
How to distinguish between a problem which is (undecidable) and which is (undecidable but partially decidable); or rather for a given problem how to say in which category it falls?
How to distinguish between a problem which is (undecidable) and which is (undecidable but partially decidable); or rather for a given problem how to say in which category...
User Avatar
1 votes
2 answers
185
Decidability
Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps. Please elaborate.
Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps.Please elaborate.
User Avatar
1 votes
3 answers
186
Decidability
Given two deterministic CFG G$_1$ and G$_2$, is L( G$_1$ ) = L( G$_2$ ) ?
Given two deterministic CFG G$_1$ and G$_2$, is L( G$_1$ ) = L( G$_2$ ) ?
User Avatar
0 votes
0 answers
187
Decidability
Given two deterministic CFG G$_1$ and G$_2$ , is L(G$_1$) ∩ L(G$_2$) = ∅ ?
Given two deterministic CFG G$_1$ and G$_2$ , is L(G$_1$) ∩ L(G$_2$) = ∅ ?
User Avatar
1 votes
1 answer
188
Reducibility Problem
Consider 2 problems X & Y. Now if X is reducible to Y.What does this mean.please explain with an example.
Consider 2 problems X & Y. Now if X is reducible to Y.What does this mean.please explain with an example.
User Avatar
0 votes
0 answers
190
Decidability Doubt
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
User Avatar
0 votes
0 answers
191
turing machine decidability
Given a turing machine M ,state q, and string 'w' whether M ever moves its head to the left when started with input w is decidable or undecidable ? explain ?
Given a turing machine M ,state q, and string 'w'whether M ever moves its head to the left when started with input wis decidable or undecidable ? explain ?
User Avatar
5 votes
1 answer
192
DECIDABILITY
L = {<M> | L(M) = {1}} L = {<M> | L(M) is {} } L = {<M> | L(M) has exactly 100 strings} which are REC R E BUT not REC , NOT EVEN RE
L = {<M | L(M) = {1}}L = {<M | L(M) is {} }L = {<M | L(M) has exactly 100 strings} which are REC R E BUT not REC , NOT EVEN RE
User Avatar
3 votes
2 answers
193
Decidability
$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$ Is $L_1$ RE or not RE?
$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$Is $L_1$ RE or not RE?
User Avatar
0 votes
1 answer
194
doubt
What is semi and Partially decidable...and how we know
What is semi and Partially decidable...and how we know
User Avatar
1 votes
1 answer
197
Decidability-12.9.5
Let $L_1$ be a regular language and G be a context-free grammar. Show that the problem "$L_1 \subseteq L(G)$" is undecidable.
Let $L_1$ be a regular language and G be a context-free grammar. Show that the problem "$L_1 \subseteq L(G)$" is undecidable.
User Avatar
1 votes
2 answers
198
Decidability
Let M1 be a Turing machine and M2 be a finite automaton. Is the problem, whether M1 and M2 accept the same language decidable? An elaborative answer with proof is most welcome.
Let M1 be a Turing machine and M2 be a finite automaton. Is the problem, whether M1 and M2 accept the same language decidable?An elaborative answer with proof is most wel...
User Avatar
0 votes
0 answers
199
TM that rejects input string x
$D = \left \{ <M> \mid \ M \text{ is a TM that rejects the input string } x \right \}$ What is complement of D and is it Decidable, Turing recognizable or not Turing recognizable?
$D = \left \{ <M \mid \ M \text{ is a TM that rejects the input string } x \right \}$What is complement of D and is it Decidable, Turing recognizable or not Turing recogn...
User Avatar
1 votes
1 answer
200
TM that accepts input string x
$D = \left \{ M \mid \ M \text{ is a TM that accepts the input string } x \right \}$ What is complement of D and is it Decidable, Turing recognizable or not Turing recognizable?
$D = \left \{ M \mid \ M \text{ is a TM that accepts the input string } x \right \}$What is complement of D and is it Decidable, Turing recognizable or not Turing recogni...
User Avatar
0 votes
0 answers
201
Decidable / Undecidable (Acceptance of CFL)
A Turing Machine accepts a language if its DCFL but rejects if it's a non deterministic CFL
A Turing Machine accepts a language if its DCFL but rejects if it's a non deterministic CFL
User Avatar
0 votes
0 answers
206
self doubt
CAN SOMEONE EXPLAIN ME WITH AN EXAMPLE THAT WHY DCFL CLOSED UNDER COMPLEMENATION AND CFL NOT CLOSED UNDER COMPLEMENATION?
CAN SOMEONE EXPLAIN ME WITH AN EXAMPLE THAT WHY DCFL CLOSED UNDER COMPLEMENATION AND CFL NOT CLOSED UNDER COMPLEMENATION?
User Avatar
0 votes
0 answers
208
TOC Decidability
How can we say that any two disjoint co-turing recognisable languages are seperable by some Decidability language?
How can we say that any two disjoint co-turing recognisable languages are seperable by some Decidability language?
User Avatar
0 votes
1 answer
210
Difference between computability and decidability
Hi, Could someone please tell the difference between computability and decidability? Thanks
Hi,Could someone please tell the difference between computability and decidability?Thanks
User Avatar
Page: