Register

Materials:

Recent questions tagged decidability

3 votes
0 answers
243
Decidability
a) L is decidable b) L is undecidable c) L is regular d) None of these
a) L is decidableb) L is undecidablec) L is regulard) None of these
User Avatar
2 votes
1 answer
245
Test Series
Explain please. Answer given is D
Explain please. Answer given is D
User Avatar
1 votes
1 answer
246
not partially decidable
what is the difference between recursive enumerable and not recursive enumerable(not partially decidable)?
what is the difference between recursive enumerable and not recursive enumerable(not partially decidable)?
User Avatar
2 votes
4 answers
247
Decidability
The problem described by the language $L = \left\{ \langle M_1,M_2 \rangle \mid L(M_1) = L(M_2) \right\}$ is a) Decidable b) Semi decidable c) not even semi-decidable
The problem described by the language $L = \left\{ \langle M_1,M_2 \rangle \mid L(M_1) = L(M_2) \right\}$ isa) Decidable b) Semi decidable c) not even semi-decidable
User Avatar
2 votes
2 answers
250
Decidability
Equality of two DPDA is decidable or undecidable ?
Equality of two DPDA is decidable or undecidable ?
User Avatar
0 votes
1 answer
251
Decidability
L= {<G> | G is CFG and G is NOT ambiguous} . L is TM recognizable or not even TM recognizable?
L= {<G | G is CFG and G is NOT ambiguous} .L is TM recognizable or not even TM recognizable?
User Avatar
1 votes
2 answers
257
Self doubt in TOC
Suppose in question we are given the language is Turing Recognizable , can I consider it a CFL or Regular?
Suppose in question we are given the language is Turing Recognizable , can I consider it a CFL or Regular?
User Avatar
3 votes
3 answers
259
Self doubt in decidability in TOC
Suppose in question we are given the language is Turing Decidable , can I consider it a CFL or Regular?
Suppose in question we are given the language is Turing Decidable , can I consider it a CFL or Regular?
User Avatar
2 votes
1 answer
260
Decidability
Which of the following decision problem is undecidable? I)Given a CFG $G=\left ( N,\Sigma ,P,S \right )$ and a string $x\epsilon \Sigma ^{*}$, does $x\epsilon L\left ( G \right )$? II) Given CFG $G_{1},G_{2}$, Is $L\left ( G_{1} \right )=L\left (G_{2} \right )$?
Which of the following decision problem is undecidable?I)Given a CFG $G=\left ( N,\Sigma ,P,S \right )$ and a string $x\epsilon \Sigma ^{*}$, does $x\epsilon L\left ( G \...
User Avatar
0 votes
1 answer
261
The Infiniteness Problem
what is the Infiniteness Problem?
what is the Infiniteness Problem?
User Avatar
3 votes
0 answers
265
Undecidability
L = {<M> | M is a TM and L(M) is infinite }..How to prove it as not RE..Here L(Tyes) = Sigma* is not subset of L(Tno) = Phi..So Rice Theorem's 2nd part is not applicable.. Can anyone please explain it ?
L = {<M | M is a TM and L(M) is infinite }..How to prove it as not RE..Here L(Tyes) = Sigma* is not subset of L(Tno) = Phi..So Rice Theorem's 2nd part is not applicable.....
User Avatar
3 votes
1 answer
266
Undecidability
L = { <M> | M is a TM and |L(M)| <= 3 }. Is it Recursively Enumerable or not ?
L = { <M | M is a TM and |L(M)| <= 3 }. Is it Recursively Enumerable or not ?
User Avatar
Page: