Recent questions tagged decidability

2 votes
2 answers
424
I want to know how to remember which language is decidable for which property. Should I go through the proofs or should I remember everything?
7 votes
2 answers
425
$L = \{\langle M \rangle \mid M\text{ is a TM and } |L(M)| \leq 3\}$.Is it decidable or undecidable?Give the approach ?
1 votes
2 answers
428
IF L IS DECIDABLE THEN1)L&L' BE TURING RECOGNIZABLE2)L MUST BE TURING RECOGNIZABLE BUT L' NEED NOT BE3)EXACTLY ONE OF L AND L' BE TURING RECOGNIZABLE4)L' IS TURING RECOGN...
2 votes
1 answer
432
0 votes
1 answer
433
Is there a one to one correspondence between problems and languages? we interchangeably use these while discussing decidabilility and turing machines
4 votes
2 answers
436
25 votes
2 answers
447
Which of the following problems is undecidable?Membership problem for CFGsAmbiguity problem for CFGsFiniteness problem for FSAsEquivalence problem for FSAs