The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
53 views
Which of the following problems are decidable?
gatecs2012automata2
A
1, 2, 3, 4
B
1, 2
c
2, 3, 4
d
3, 4
closed as a duplicate of: GATE2012_24
asked in Theory of Computation by (251 points)
closed by | 53 views
Posting a duplicate question loses 50 points and when the point goes below 10, posting right will be gone.

1 Answer

0 votes

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..

answered by Veteran (96.7k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,156 questions
36,980 answers
92,146 comments
34,822 users