GATE CSE 2008 | Question: 48

Question

Which of the following statements is false?

• A. Every NFA can be converted to an equivalent DFA

• B. Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine

• C. Every regular language is also a context-free language

• D. Every subset of a recursively enumerable set is recursive

Comments

In option D we can’t even say that every subset of RE is RE.

---

as recursive set is proper subset of recursively enumerable language, so there exists a language whihc is re but not rec

---

@Pratik2404 is correct as :

Every infinite language has a subset which is non RE/unrecognizable.. (undecidable). 
reference: https://gateoverflow.in/357504/gate-cse-2021-set-2-question-36?show=357698#a357698

Answer 1

There exists a set of languages which is RE but not REC ( i.e. Recursively Enumerable but not Recursive), this set is a subset of RE but is Not Recursive.

Option D tells us that every subset of RE is REC this is false.
Hence, option D is chosen.

Comments

is B correct?

every non-deterministic  turning machine is equal to deterministic one.?

---

yes, but it is "equivalent" not "equal". Equal requires them to be exactly same- which is not. But they are equivalent in the sense that both accept the same class of languages - recursively enumerable set.

Answer 2

A language is recursively enumerable if there exists a Turing machine that accepts every string of the language, and does not accept strings that are not in the language. Strings that are not in the language may be rejected or may cause the Turing machine to go into an infinite loop.
A recursive language can't go into an infinite loop, it has to clearly reject the string, but a recursively enumerable language can go into an infinite loop.
So, every recursive language is also recursively enumerable. Thus, the statement ‘Every subset of a recursively enumerable set is recursive’ is false.
 
Thus, option (D) is the answer.

Answer 3

Every NFA can be converted into DFA (as there exist a standard procedure to convert NFA into DFA). Also, every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine. Every regular language is also a CFL , since if a language can be recognized by Finite automata, then it must also be recognize by PDA (as PDA is more powerful than FA). But every subset of recursively enumerable need not be recursive.

Answer 4

(D) is correct answer

Comments

Yes. $\Sigma^*$ is recursively enumerable and any non recursively language must be a subset of this.

---

Do recursively enumerable language and recursive language are synonyms or different?

Answer 5

Option A is true, because there is an algorithm (subset construction method) to convert any NFA to an equivalent DFA.

Option B is true, because Deterministic TM and Non-deterministic TM are equivalent in power.

Option C is true, by definition, every regular language is a context free language.

Option D is False, for multiple reasons:

1. Subset operation is not closed for Recursively Enumerable Languages (RELs), i.e subset of a REL need not be REL, so it need not be recursive.
2. Also, there are languages that have a TM but don’t have a halting TM, i.e they are REL but not recursive, so there is no way that subset of such a language is recursive.