+1 vote
35 views
Which of the following problems are decidable?
 A 1, 2, 3, 4 B 1, 2 c 2, 3, 4 d 3, 4
closed as a duplicate of: GATE2012_24
closed | 35 views
Posting a duplicate question loses 50 points and when the point goes below 10, posting right will be gone.

Lets see the options one by one..

1)  is undecidable..This can be correlated to computability of Turing machine..Specifically halting property of Turing Machine which is undecidable..

2) option is also undecidable as complement of context free language may or may not be context free language..So we cannot say with surety that for the class of context free languages , the complementary language will also be context free..

3) and 4)  are decidable as regular and recursive languages are closed under complementation..

Hence D) should be correct answer..