754 views
5 votes
5 votes
Which is correct?

I) All recursive enumerable language would be recursive, if halting problem is decidable

II) For any CFG, it is undecidable whether or not a particular non terminal "X" in G is reachable

a) I is correct but II is incorrect

b) II is correct but I is incorrect

c) Both are correct

d) Both are incorrect

1 Answer

Best answer
3 votes
3 votes

For statement 1 , we need to know about the reduction theorem :

In   X  <m   Y  , if Y is known to be RE then X will be RE . Also if Y is known to be REC , then X will also be REC . Hence all problems reducible to halting problem will be RE as per the normal case as halting problem is RE but not REC . 

But if Y which is a halting problem in this case were decidable , it means Y is recursive and hence any problem reducing to Y will be recursive specifically rather than simply RE . 

Hence in this case , all recursively enumerable languages will become recursive language .Hence statement 1 is true.

For statement 2 , we know that the given problem has algorithm to solve and hence decidable . In this first we have to identify the start symbol , then identify the set of non terminals that are part of production of this start symbol ; directly or indirectly . Hence we can say whether a given non terminal in the context free grammar G is reachable or not.

Hence the given problem is decidable and this makes statement 2 false. Thus A) should be the correct option.

selected by

Related questions

0 votes
0 votes
0 answers
4
Xylene asked Sep 9, 2017
192 views
I think that answer should be decidable.