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

Which of the following statements is/are FALSE?

  1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
  2. Turing recognizable languages are closed under union and complementation.
  3. Turing decidable languages are closed under intersection and complementation.
  4. Turing recognizable languages are closed under union and intersection.
     

 

  1. 1 and 4 only    
  2. 1 and 3 only    
  3. 2 only    
  4. 3 only
asked in Theory of Computation by Veteran (346k points)
edited by | 1.8k views
Sir , please correct me

Recursive Enumerable for TM is possible

if L belongs to RE, then we apply any string to TM -> either it says YES or(NO or INFINITE LOOP)

But for L(complement) { Language out side the RE and within the SET of all LANGUAGES)

TM is not possible for such language , therefore RE is not come under COMPLEMENT

 

 

Similar for SET DIFFERENCE,

please correct me !

4 Answers

+27 votes
Best answer

Recursive enumerable languages are not closed under complement . while recursive languages are.

both Recursive and Recursive enumerable languages are closed under intersection, union, and kleene star.

http://gatecse.in/wiki/Closure_Property_of_Language_Families

Non-Deterministic TM is equivalent to DTM

only 2 is false. Option C is correct.

 

Note: Turing decidable language mean Recursive language and Turing recognizable language mean recursive enumerable language.

answered by Veteran (55.2k points)
edited by
given link is not working
+6 votes

Answer is (C) Part.

For every point i am mentioning some small intuition or some hint as per my knowledge which may help readers -->

For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.

If something is computable then there exists a DTM(Deterministic Turing Machine) for it. 

Turing recognizable languages are closed under union and complementation.

Turing recognizable languages are known as RE languages whose complement may not be RE. But RE languages are closed under Intersection and Union.

Turing decidable languages are closed under intersection and complementation

Turing decidable languages means REC( or recursive languages). We have HTM(Halting Turing Machine) corresponding to REC.

For proof please refer --> http://www.eecs.wsu.edu/~cook/tcs/l19.html

Just for recalling a quick table is mentioned on --> https://gatecse.in/closure-property-of-language-families/

answered by Veteran (14.7k points)
edited by
+2 votes

Option A  - A nondeterministic Turing machine is a generalization of the standard TM for which every configuration may yield none, or one or more than one next configurations. reference : -http://www.cs.rpi.edu/~goldberg/14-CC/02-ndt.pdf

Option B   Turing recognizable language ( Recursive Enumerable language ) is not closed under complementation because as given in figure we can see if we complement it then we don't know about loop  but closed under union 

 

 Option 3- Turing Decidable language means Recursive language so it is closed under Complementation why we can see in figure

 

as well as if is closed under intersection as given figure 

Option 4 is also true because we can find intersection of two RE language as well union as previous figure 

*There is little modification in figure 1 which is there is loop in outer block 

Hence option 2 is FALSE

answered by Veteran (11.2k points)
edited by
+1 vote
(C) 2 only
answered by Boss (6.3k points)


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

33,687 questions
40,231 answers
114,271 comments
38,803 users