The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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

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

+3 votes

Best answer

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 statemen*t

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 487
- Exam Queries 436
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,194 questions

43,647 answers

124,088 comments

42,929 users