GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
35 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 (403 points)  
closed by | 35 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 (76.3k points)  


Top Users Sep 2017
  1. Habibkhan

    6362 Points

  2. Warrior

    2234 Points

  3. Arjun

    2212 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1716 Points

  8. makhdoom ghaya

    1660 Points

  9. A_i_$_h

    1552 Points

  10. rishu_darkshadow

    1512 Points


25,991 questions
33,561 answers
79,414 comments
31,029 users