The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+4 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

+2 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.1k
- Engineering Mathematics 4k
- Digital Logic 1.7k
- Programming & DS 3k
- Algorithms 2.6k
- Theory of Computation 3.2k
- Compiler Design 1.2k
- Databases 2.4k
- CO & Architecture 2.1k
- Computer Networks 2.4k
- Non GATE 819
- Others 1.1k
- Admissions 244
- Exam Queries 420
- Tier 1 Placement Questions 16
- Job Queries 39
- Projects 4

29,157 questions

36,984 answers

92,154 comments

34,823 users