The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.4k views

Which of the following statements is false?

  1. Every NFA can be converted to an equivalent DFA

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

  3. Every regular language is also a context-free language

  4. Every subset of a recursively enumerable set is recursive

asked in Theory of Computation by Veteran (59.4k points)
retagged by | 1.4k views

3 Answers

+18 votes
Best answer

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.

answered by Boss (30.5k points)
edited by
0
is B correct?

every non-deterministic  turning machine is equal to deterministic one.?
+2
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.
+6 votes
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.
answered by Loyal (8.1k points)
+2 votes
(D) is correct answer
answered by Loyal (6.1k points)
edited by
+5
Yes. $\Sigma^*$ is recursively enumerable and any non recursively language must be a subset of this.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,202 questions
43,662 answers
124,114 comments
42,944 users